解题思路:
n个位置最多种植n/2棵树,n可奇可偶
如果位置1一定需要种植一棵树,那么位置2,n一定不可以种植树,
那么需要在3-(n-1)的位置种植m-1棵树.
因为此时最大价值=dp[n-1][m-1]+A[1]
如果位置1不种树,那么2-n的位置都可以种植树木
因为此时最大值为dp[n][m]
最后从两者取最优方案
res1 = dp1[n-1][m-1]+A[1]; res2 = dp2[n][m]; res = max(res1,res2);
注意事项:
边界处理需要细心一点
参考代码:
#include<iostream> #include<algorithm> using namespace std; const int N = 31,MIN=-0x3FFFFFFF; int dp1[N][N],dp2[N][N],A[N]; int main(void) { int n,m,res1,res2,res; cin>>n>>m; for(int i=1;i<=n;i++) cin>>A[i]; //n个位置最多种植n/2棵树,n可奇可偶 if(m>n/2) { cout<<"Error!"; return 0; } for(int j=1;j<=m-1;j++) dp1[0][j]=dp1[1][j]=dp1[2][j]=MIN; /* 如果位置1一定需要种植一棵树,那么位置2,n一定不可以种植树, 那么需要在3-(n-1)的位置种植m-1棵树. 因为此时最大价值=dp[n-1][m-1]+A[1] */ for(int i=3;i<=n-1;i++)//i=1,2,n不需要处理 { for(int j=1;j<=m-1;j++)//1位置一定确定种植一棵树,故只需要寻找m-1棵 { dp1[i][j]=max(dp1[i-2][j-1]+A[i],dp1[i-1][j]); } } for(int j=1;j<=m;j++) dp2[0][j]=dp2[1][j]=MIN; /* 如果位置1不种树,那么2-n的位置都可以种植树木 因为此时最大值为dp[n][m] */ for(int i=2;i<=n;i++)//i=1不需要处理 { for(int j=1;j<=m;j++) { dp2[i][j]=max(dp2[i-2][j-1]+A[i],dp2[i-1][j]); } } res1 = dp1[n-1][m-1]+A[1]; res2 = dp2[n][m]; res = max(res1,res2); cout<<res; return 0; }
0.0分
6 人评分
#include<stdio.h> int a[100000]; int n,m; int MAX(int a[]) { int i=0,k; int max=0; for(;i<n;i++){ if(a[i]>max) { max=a[i]; k=i; } } return max; } int main() { int sum=0,j; scanf("%d%d",&n,&m); if(n/2>=m) { for(int i=0;i<n;i++){ scanf("%d",&a[i]); } int b[n]={0}; while(1){ for(j=0;j<n;j++){ if(a[j]==MAX(a)) break; } if(j==0){ if(b[1]==0&&b[n-1]==0){ b[j]=1; sum=sum+a[j]; a[j]=0; m--; } } if(j==n-1){ if(b[0]==0&&b[n-2]==0){ b[j]=1; sum=sum+a[j]; a[j]=0; m--; } } if(j!=0&&j!=n-
C语言程序设计教程(第三版)课后习题12.1 (C语言代码)浏览:973 |
程序员的表白 (C语言代码)浏览:1455 |
2005年春浙江省计算机等级考试二级C 编程题(3) (C语言代码)浏览:385 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:531 |
众数问题 (C语言代码)浏览:820 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:632 |
字符逆序 (C语言代码)浏览:455 |
1128题解(返回值为数组的情况)浏览:450 |
C语言训练-亲密数 (C语言描述,反正怎么都能对)浏览:2154 |
C二级辅导-阶乘数列 (C语言代码)浏览:507 |