cug上的几道dp题

news/2023/6/5 20:54:33

题目链接:http://acm.cug.edu.cn/JudgeOnline/problem.php?id=1317

思路:dp[i][j]表示以a[i]为结尾的串与以b[j]为结尾的串的最小编辑距离,则

若a[i]==a[j],有dp[i][j]==dp[i-1][j-1];

否则dp[i][j]=min{dp[i-1][j-1]+2,dp[i-1][j]+3,dp[i][j-1]+3}

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<string>
 5 #include<algorithm>
 6 using namespace std;
 7 #define inf 1<<30
 8 int dp[1010][1010];
 9 char str[1010];
10 char ss[1010];
11 
12 
13 int main(){
14     while(~scanf("%s",str)){
15         int _case,len=strlen(str),ans=inf;
16         string s;
17         scanf("%d",&_case);
18         while(_case--){
19             scanf("%s",ss);
20             int ll=strlen(ss);
21             for(int i=0;i<=len;i++)
22                 for(int j=0;j<=ll;j++)
23                     dp[i][j]=inf;
24             dp[0][0]=0;
25             dp[0][1]=dp[1][0]=3;
26             for(int i=1;i<=len;i++){
27                 for(int j=1;j<=ll;j++){
28                     if(str[i-1]==ss[j-1]){
29                         dp[i][j]=dp[i-1][j-1];
30                     }else 
31                         dp[i][j]=min(dp[i-1][j-1]+2,min(dp[i-1][j]+3,dp[i][j-1]+3));
32                 }
33             }
34             if(ans>dp[len][ll]){ ans=dp[len][ll],s=ss; }
35         }
36         cout<<ans<<endl;
37         cout<<s<<endl;
38     }
39     return 0;
40 }
View Code

 题目链接:http://acm.cug.edu.cn/JudgeOnline/problem.php?id=1318

思路:就是求最长上升子序列,不过要先对x进行排序。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 struct Node{
 7     int x,y;
 8 }node[1111];
 9 int dp[1111];
10 
11 int cmp(const Node &p,const Node &q){
12     return p.x<q.x;
13 }
14 
15 int main(){
16     int n,ans;
17     while(~scanf("%d",&n)){
18         for(int i=0;i<n;i++){
19             scanf("%d%d",&node[i].x,&node[i].y);
20         }
21         sort(node,node+n,cmp);
22         memset(dp,0,sizeof(dp));
23         dp[0]=1;
24         for(int i=1;i<n;i++){
25             ans=0;
26             for(int j=0;j<i;j++){
27                 if(node[i].y>node[j].y&&ans<dp[j])
28                     ans=dp[j];
29             }
30             dp[i]=ans+1;
31         }
32         ans=0;
33         for(int i=0;i<n;i++)ans=max(ans,dp[i]);
34         printf("%d\n",ans);
35     }
36     return 0;
37 }
38 
39         
View Code

 

转载于:https://www.cnblogs.com/wally/archive/2013/05/21/3091113.html


https://dhexx.cn/news/show-18590.html

相关文章

微信小程序语言c#,微信小程序推出最新脚本语言WXS,你需要知道的全在这里了...

原标题&#xff1a;微信小程序推出最新脚本语言WXS&#xff0c;你需要知道的全在这里了感谢“造程序”(微信ID&#xff1a;zaochengxucom)的授权发布。责编&#xff1a;陈秋歌&#xff0c;关注微信开发等领域&#xff0c;寻求报道或者投稿请发邮件至chenqg#csdn.net。WXS脚本语…

Preference+PreferenceArray+DataModel

在Mahout中&#xff0c;用户的喜好被抽象为一个Preference&#xff0c;包含了userId&#xff0c;itemId和偏好值&#xff08;user对item的偏好&#xff09;。Preference是一个接口&#xff0c;它有一个通用的实现是GenericPreference。 因为用户的喜好数据是大规模的&#xff0…

android 向js传递参数,《成为大前端》系列 4.4 Native与JS通信-参数传递和结果返回(Android)...

JS 传递参数到 Native前面完成了 JS 调用 Native&#xff0c;接下来继续 JS 如何传递参数到 Native传递原始类型数据先看 JS 端的代码&#xff1a;function onClickButton(){window.androidBridge.callNative("Hello");}复制代码Native 端&#xff1a;inner class Br…

2013第四届 蓝桥杯c/c++B组预赛 解题报告(还在更新中。。。。。)

大半部分题目都是自己做的&#xff0c;可能还有存在错误的地方&#xff0c;还望各位指正。 有不会的题目&#xff0c;还请大牛们留下解题思路&#xff0c;谢谢了。 第一题&#xff1a;高斯日记 大数学家高斯有个好习惯&#xff1a;无论如何都要记日记。他的日记有个与众不同的地…

android读取多行文件,Android 读取txt,按行读取的实例讲解

Android 读取txt,按行读取的实例讲解发布时间&#xff1a;2020-09-12 12:43:31来源&#xff1a;脚本之家阅读&#xff1a;103作者&#xff1a;Damionew一个TXT 文件 对其进行读取&#xff0c;并且每行都单个存储读取public class MainActivity extends AppCompatActivity {priv…

Java简单游戏开发之碰撞检测

前言 不久之前在论坛上有人发贴&#xff0c;使用java编写的超级马里奥如何实现碰撞检测&#xff0c;笔者自己以前 也做过Tank大战。里面同样涉及到碰撞检测&#xff0c;翻翻U盘里的东西还在&#xff0c;什么时候也给共享出来。 这篇文章就简单游戏中的碰撞检测做一个简单的总结…

通用用户权限管理系统组件V3.9功能改进说明 - 操作权限项定义简化

在通用权限管理系统组件V3.9中对操作权限项定义进行了一次大胆的简化&#xff0c;现在定义模块菜单的同时可以定义操作权限项目&#xff0c;这样不用菜单与操作权限分离了&#xff0c;可以集中展示&#xff0c;实用效果更加友善。 下面是定义菜单或者操作权限项目的参考页面 设…

html 10 margin 重叠

留意&#xff0c;父子元素&#xff0c;margin重叠影响的是margin-top上的。取两者中的最大值&#xff0c;水平和bottom不受影响&#xff0c; 重叠的时候子元素的margin-top消失 父元素如果加了padding属性&#xff0c;不会重叠。子元素如果有float&#xff0c;父子不重叠 CSS 外…

PHP cURL模块

简介&#xff1a; cURL是利用URL语法在命令行方式下工作的文件传输工具&#xff0c;目前苹果机器已经内置了cURL。cURL是一个综合性的传输工具&#xff0c;对HTTP、FTP等协议提供了广泛的支持&#xff0c;它甚至可以实现迅雷、快车等下载工具的所有功能。PHP中也提供了对cURL语…

day20(下)_IO流5(递归穷举与删除,Properties,PrintStream,PrintWriter,SequenceInputStream)

1.对目录和文件递归穷举 /* 列出指定目录下的文件或者文件夹,包含子目录中的内容 也就是列出目录下所有的内容 例如:new File(d:\\);在d盘下还有一个abc目录而abc下还有文件和目录,而用list()方法只能获取到d盘下的文件和目录 */ package filedemo; import java.util.Arrays; i…