http://acm.hdu.edu.cn/showproblem.php?pid=2845
题意:有一个n*m的矩阵,每个矩阵里都有一个值且为正。当选择一个数(x,y),那么就不能加(x,y-1),(x,y+1)以及x-1行和x+1行的数。问最后这个矩阵的最大和是多少?
思路:对于每一行,求最大不连续子序列之和。dp[i] = max( dp[i-2]+row[i], dp[i-1] )。这样求出每一行的最大和之后,再对列进行同样的处理。
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn = 200010; int row[maxn],col[maxn]; int dp[maxn],dp2[maxn]; int main() { int n,m; while(~scanf("%d %d",&n,&m)) { memset(dp2,0,sizeof(dp2)); for(int i = 1; i <= n; i++) { memset(dp,0,sizeof(dp)); for(int j = 1; j <= m; j++) scanf("%d",&row[j]); dp[1] = row[1]; for(int j = 2; j <= m; j++) dp[j] = max(dp[j-2]+row[j],dp[j-1]); //对每一行求最大不连续子序列和 if(i == 1) dp2[i] = dp[m]; else dp2[i] = max(dp2[i-2]+dp[m], dp2[i-1]);//再对列求最大不连续子序列和 } printf("%d\n",dp2[n]); } return 0; }