思路:假设我们先只考虑一行,规则就是取了i处的土豆,每一个土豆有两种选择,拿与不拿,那么i-1和i+1处的土豆都不能再取,那么要求某一行的最大取值就用一次动态规划即可,dp(i)表示前i个土豆能取得的最大值,转移方程dp(i) = max{dp(i-1), dp(i-2) + w[i]},此时我们已经得到了每一行的最优解,然后可以把n行看做是n个土豆,即每一行看做最优值土豆,同样的状态方程。此题很妙。
AC代码
#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 500 + 5; int w[maxn][maxn], sum[maxn][maxn], dp[maxn]; int main() { int n, m; while(scanf("%d%d", &n, &m) == 2) { for(int i = 0; i < n; ++i) { for(int j = 0; j < m; ++j) { scanf("%d", &w[i][j]); sum[i][j] = j==0?0:sum[i][j-1]; int pre; if(j-2 < 0) pre = 0; else pre = sum[i][j-2]; sum[i][j] = max(sum[i][j], pre + w[i][j]); } } for(int i = 0; i < n; ++i) { dp[i] = i == 0 ? 0 : dp[i-1]; int pre; if(i-2 < 0) pre = 0; else pre = dp[i-2]; dp[i] = max(dp[i], pre + sum[i][m-1]); } printf("%d\n", dp[n-1]); } return 0; }
如有不当之处欢迎指出!