题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2845
题意：给你一个矩阵，如果取num[i][j], 那么num[i - 1][], num[i + 1][j], num[i][j - 1], num[i][j + 1]都会被删除， 问取得数的最大和是多少？
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <set> 8 #include <map> 9 #include <vector> 10 #define LL long long 11 using namespace std; 12 13 const int N = 2 * 1e5 + 10; 14 LL r[N], num[N], dp[5]; 15 int main() 16 { 17 int n, m; 18 while(~scanf("%d %d", &m, &n)) 19 { 20 for(int i = 1; i <= m; i++) 21 { 22 dp[0] = 0; 23 for(int j = 1; j <= n; j++) 24 { 25 scanf("%lld", r + j); 26 if(j == 1) 27 dp[1] = r[1]; 28 if(j == 2) 29 dp[2] = max(dp[1], r[2]); 30 if(j > 2) 31 dp[j % 3] = max(dp[(j - 1) % 3], max(dp[(j - 2) % 3], dp[(j - 3) % 3]) + r[j]); 32 // cout << dp[0] << " "<< dp[1] << " " << dp[2] << " "; 33 } 34 num[i] = dp[n % 3]; 35 //cout <<num[i] << endl; 36 } 37 dp[0] = 0; 38 for(int j = 1; j <= m; j++){ 39 if(j == 1) 40 dp[1] = num[1]; 41 if(j == 2) 42 dp[2] = max(num[1], num[2]); 43 dp[j % 3] = max(dp[(j - 1) % 3], max(dp[(j - 2) % 3], dp[(j - 3) % 3]) + num[j]); 44 } 45 printf("%lld ", dp[m % 3]); 46 } 47 return 0; 48 }