cug上的几道dp题

题目链接：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