2009 Multi-University Training Contest 4 – Host by HDU题目链接：?pid=2845题目大意：在一个矩阵中选择一些数，要求和最大，如果选择(x,y)位置的数，则(x, y+1)，(x,y-1)位置不可选，第x+1和第x-1行都不可选题目分析：题目给了m*n的范围，就是不让你开二维开开心心切掉，不过不影响，一维照样做，先对于每一行dp一下，，求出当前行能取得的最大值tmp[j] = max(tmp[j – 1]，a[i + j – 1] + tmp[j – 2])第一个表示不选第i行第j列得数字，第二个表示选，取最大，则最后tmp[m]为当前行最大的然后因为相邻两行不能同时取，我再对行做一次dpdp[i] = max(dp[i – 1], dp[i – 2] + row[i])，第一个表示不选第i行，第二个表示选第i行，取最大，则最后dp[cnt – 1]即为答案#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int const MAX = 2 * 1e5 + 5;int row[MAX], a[MAX], dp[MAX], tmp[MAX];int main(){int n, m;while(scanf("%d %d", &n, &m) != EOF){memset(tmp, 0, sizeof(tmp));memset(dp, 0, sizeof(dp));for(int i = 1; i <= m * n; i++)scanf("%d", &a[i]);int cnt = 1;for(int i = 1; i <= m * n; i += m){for(int j = 2; j <= m; j++){tmp[1] = a[i];tmp[j] = max(tmp[j – 1], a[i + j – 1] + tmp[j – 2]);}row[cnt ++] = tmp[m];}dp[1] = row[1];for(int i = 2; i < cnt; i++)dp[i] = max(dp[i – 1], dp[i – 2] + row[i]);printf("%d\n", dp[cnt – 1]);}}
为我祈祷平安就好。我的旅行，会有你们的故事陪伴，所以我不会孤单。放心吧。
