2018.02.02(登山，怪盗基德的滑翔翼等)

2018.02.02

动态规划练习

1.登山

思路：就是一个同时找最长上升子序列和最长下降子序列的综合题。最后加起来取最大值。不过需要注意的是，不管是上山还是下山，第一个点都是要初始化的，这是边界条件。因为下山没有初始化，调了2h+的教训要记得。

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int n,num[1001],sum_up[1001],sum_down[1001];
 5 int max=1;
 6 int _Max(int x,int y){return x>y?x:y;} 
 7 int main(){
 8     scanf("%d",&n);
 9     int i,j;
10     for(i=1;i<=n;i++)
11         scanf("%d",&num[i]);
12     sum_up[1]=1;
13     for(i=2;i<=n;i++){
14         sum_up[i]=1;
15         for(j=i-1;j>0;j--)
16             if(num[j]<num[i])
17                 sum_up[i]=_Max(sum_up[i],sum_up[j]+1);
18     }
19     sum_down[n]=1;
20     for(i=n-1;i>0;i--){
21         sum_down[i]=1;
22         for(j=i+1;j<=n;j++)
23             if(num[j]<num[i])
24                 sum_down[i]=_Max(sum_down[i],sum_down[j]+1);
25         max=_Max(max,sum_up[i]+sum_down[i]-1);
26     }
27     max=_Max(max,sum_up[n]+sum_down[n]-1);
28     printf("%d",max);
29     return 0;
30 }

View Code

状态：AC

2.怪盗基德的滑翔翼

思路：也是一个同时找最长上升子序列和最长下降子序列的综合题。不过这个题不是加起来，而是两条最优方案再取最优。

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int n,num[1001];
 5 int sum[1001],sum2[1001];
 6 int max=-99999999;
 7 int _Max(int x,int y){return x>y?x:y;} 
 8 int main(){
 9     int kk;
10     scanf("%d",&kk);
11     for(int k=1;k<=kk;k++){
12         scanf("%d",&n);
13         int i,j;
14         for(i=1;i<=n;i++)
15             scanf("%d",&num[i]);
16         sum[1]=1;
17         for(i=2;i<=n;i++){
18             sum[i]=1;
19             for(j=1;j<i;j++)
20                 if(num[j]>num[i])
21                     sum[i]=_Max(sum[i],sum[j]+1);
22         }
23         sum2[1]=1;
24         for(i=2;i<=n;i++){
25             sum2[i]=1;
26             for(j=1;j<i;j++)
27                 if(num[j]<num[i])
28                     sum2[i]=_Max(sum2[i],sum2[j]+1);
29         }
30         for(i=1;i<=n;i++){
31             max=_Max(max,sum[i]);
32             max=_Max(max,sum2[i]);
33         }
34         printf("%d
",max);
35         max=-99999999;
36     }
37     return 0;
38 }

View Code

状态：AC

3.移动路线

思路：数字三角形的变式，状态转移方程都是一样的。

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int map[21][21];
 5 int n,m;
 6 main(){
 7     scanf("%d%d",&n,&m);
 8     int i,j;
 9     map[0][1]=1;
10     for(i=1;i<=n;i++)
11         for(j=1;j<=m;j++)
12             map[i][j]=map[i-1][j]+map[i][j-1];
13     printf("%d",map[n][m]);
14     return 0;
15 }

View Code

状态：AC

4.最低通行费

思路：同(3)。只不过要额外加一个边界判定条件：2*n-1的时间，在找最短路时不能超时。

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int map[101][101],f[101][101];
 5 int n;
 6 int _Min(int x,int y){return x<y?x:y;}
 7 void search(int time,int x,int y){
 8     if(time==0&&(x!=n||y!=n))
 9         return;
10     if(f[x-1][y]==-1 &&x-1>=1)
11         search(time-1,x-1,y);
12     if(f[x][y-1]==-1 &&y-1>=1)
13         search(time-1,x,y-1);
14     if(x-1>=1&&y-1>=1)
15         f[x][y]=map[x][y]+_Min(f[x][y-1],f[x-1][y]);
16     else if(x-1>=1&&y-1<1)
17         f[x][y]=map[x][y]+f[x-1][y];
18     else if(x-1<1&&y-1>=1)
19         f[x][y]=map[x][y]+f[x][y-1];
20 }
21 int main(){
22     scanf("%d",&n);
23     int i,j;
24     for(i=1;i<=n;i++){
25         for(j=1;j<=n;j++){
26             scanf("%d",&map[i][j]);
27             f[i][j]=-1;
28         }
29     }
30     f[1][1]=map[1][1];
31     search(2*n-1,n,n);
32     printf("%d
",f[n][n]); 
33     return 0;
34 }

View Code

状态：AC

5.摘花生

思路：还是数字三角形。(话说好像做的都是同一个模板题)

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int map[101][101],f[101][101];
 5 int n,m;
 6 int _Max(int x,int y){return x>y?x:y;}
 7 void search(int x,int y){
 8     if(x<1||y<1)
 9         return;
10     if(f[x-1][y]==-1 &&x-1>=1)
11         search(x-1,y);
12     if(f[x][y-1]==-1 &&y-1>=1)
13         search(x,y-1);
14     if(x-1>=1&&y-1>=1)
15         f[x][y]=map[x][y]+_Max(f[x-1][y],f[x][y-1]);
16     else if(x-1>=1&&y-1<1)
17         f[x][y]=map[x][y]+f[x-1][y];
18     else if(x-1<1&&y-1>=1)
19         f[x][y]=map[x][y]+f[x][y-1];
20 }
21 int main(){
22     int k;
23     int i,j;
24     scanf("%d",&k);
25     for(int kk=1;kk<=k;kk++){
26         scanf("%d%d",&n,&m);
27         for(i=1;i<=n;i++){
28             for(j=1;j<=m;j++){
29                 scanf("%d",&map[i][j]);
30                 f[i][j]=-1;
31             }
32         }
33         f[1][1]=map[1][1];
34         search(n,m);
35         printf("%d
",f[n][m]);
36     }
37     return 0;
38 }

View Code

状态：AC

6.Maxinum sum

状态：UNAC

7.计算字符串距离

状态：UNAC

8.公共子序列

题解代码：

 1 #include <cstdio>
 2 #include<cmath>
 3 #include<cstring>
 4 #include<iostream>
 5 using namespace std;
 6 int main(){
 7     char a[210],b[210];
 8     int f[201][201];
 9     int l1,l2,i,j;
10     while(cin>>a+1>>b+1){
11         memset(f,0,sizeof(f));
12         l1=strlen(a);
13         l2=strlen(b);
14         for(i=1;i<l1;i++)
15             for(j=1;j<l2;j++)
16                 if(a[i]==b[j]&&f[i-1][j-1]+1>f[i][j])
17                     f[i][j]=f[i-1][j-1]+1;
18                 else
19                     f[i][j]=max(f[i-1][j],f[i][j-1]);
20         cout<<f[l1-1][l2-1]<<endl;
21     }
22     return 0;
23 }

View Code

状态：UNAC(照着书上打了一上午，还是过不了？借鉴了一个题解，评测可以过，本地过不了？？？)