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