题意:如图中所示,选一个数后,它左右两边的数 和 上下2行的数不能再选,问这样选出的数和的最大值
思路:对每一行求出:这一行选数字的最大值(也就是 i行 做一个最大值dp[i] ,则这一行的最大值是 dp[i][m] )
对列来求dp时 ,已知每一行的最值是 dp[i][m],则这里做一个小dp2
mark
#include <stdio.h> #include <string.h> #define N 2000 int n,m,temp; int dp[N][N],dp2[N]; inline int Max(int a,int b){return a>b?a:b;} int main(){ int i,j,k; while(~scanf("%d %d",&n,&m)){ memset(dp[0],0,sizeof(dp[0])); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&temp); dp[i][j]=Max(temp,dp[i][j-1]); for(k=1;k<=j-2;k++) dp[i][j]=Max(dp[i][k]+temp,dp[i][j]); } int ans=0; for(i=1;i<=n;i++) { dp2[i]=dp[i][m]; for(j=1;j<=i-2;j++) dp2[i]=Max(dp2[i],dp2[j]+dp[i][m]); ans=Max(ans,dp2[i]); } printf("%d\n",ans); } return 0; }