题目链接：HDOJ 2845
刚开始有点迷，后来发现这就是最大不连续子序列和的二维变形.......
因为选定一个点， 和他同行相邻的点不能选定，且和它列数相邻的也不可选，全局考虑下，就是先求一维的最大不连续序列和，然后 再对所求序列和组成序列求和。。。结束
代码：
#include<cstdio> #include<queue> #include<cstring> #include<string> #include<stack> using namespace std; #define M(a) memset(a,0,sizeof(a)) #define Max(a,b) ((a>b)?a:b) #define Min(a,b) ((a<b)?a:b) #define debug 0 const int maxn = 200000 + 5; int data[maxn], dp[maxn]; int n, m; int Do(int a[], int len){ int f[maxn], t[maxn]; f[0] = t[0] = 0; f[1] = t[1] = a[1]; for (int i = 2; i <= len; i++){ t[i] = f[i - 2] + a[i]; f[i] = Max(t[i], f[i - 1]); } return f[len]; } int main() { #if debug freopen("in.txt", "r", stdin); #endif//debug while (~scanf("%d%d", &n, &m)) { M(dp); M(data); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%d", &data[j]); } dp[i] = Do(data, m); } printf("%d\n", Do(dp, n)); } return 0; }
