2018.01.07(最长上升子序列，拦截导弹等)

2018.01.07

动态规划练习

思路：思路和最长上升子序列是差不多的，只不过两个题目要求的东西不一样，一个是求的长度(即最长上升子序列)，一个是求的子序列和。这样就要注意一个点：最长的上升子序列之和不一定最大。

状态转移方程：sum[i]=_Max(sum[i],sum[j]+num[i]); (j<i，num[j]<num[i])

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int n,num[1001],sum[1001];
 5 int max=0;
 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[i]=num[i];
13         for(j=i-1;j>=1;j--){
14             if(num[j]<num[i]){
15                 sum[i]=_Max(sum[i],sum[j]+num[i]);
16             }
17         }
18     }
19     for(i=1;i<=n;i++)
20         max=_Max(max,sum[i]);
21     printf("%d",max);
22     return 0;
23 }

View Code

状态：AC

2.拦截导弹

思路：本质是最长不上升子序列，所以可以把最长上升子序列的代码直接copy，因为区别不大，思路就不具体讲解。

状态转移方程：sum[i]=_Max(sum[i],sum[j]+1); (j<i，num[j]<num[i])

核心代码：

 1 #include <stdio.h>
 2 #include <math.h>
 3 #include <string.h>
 4 int n,num[1001],sum[1001];
 5 int max=-99999999;
 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[1]=1;
13     for(i=2;i<=n;i++){
14         sum[i]=1;
15         for(j=1;j<i;j++){
16             if(num[j]>num[i]){//和最长上升子序列唯一不同的就是一个大于号(滑稽
17                 sum[i]=_Max(sum[i],sum[j]+1);
18             }
19         }
20     }
21     for(i=1;i<=n;i++)
22         max=_Max(max,sum[i]);
23     printf("%d",max);
24     return 0;
25 }

View Code

状态：AC

3.移动路线

思路：题目中说是只能往上或往右走，那么对于任意一个点，它可以由它下面和它左边的点走到，则可以到达这个点的路径总和就是它下面和它左边的点的路径之和。要注意的是，对于起点，要进行特判，把他的路径条数设为1。

核心代码：

 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

状态转移方程：map[i][j]=map[i-1][j]+map[i][j-1]

状态：AC