HDU 1024 Max Sum Plus Plus——♂简单♂DP

HDU 1024 Max Sum Plus Plus——♂简单♂DP

这题不是很好想，当时卡在这个题上主要是思维定式了，我看这个题的大体思路以及滚动数组的优化很像01背包，就按照01背包的大体思路来想了，这就导致我一直不明白为什么m要套在外层循环，为什么要对n进行压缩，后来翻了两页博客直到看到下面这位大佬的博客才明白：

​

#include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 1e6 + 10;int n, m, temp, a[maxn], dp[maxn], maxv[maxn];int main(){ while (scanf("%d %d", &m, &n) == 2) { memset(dp, 0, sizeof(dp)); memset(maxv, 0, sizeof(maxv)); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } for (int i = 1; i <= m; i++) { temp = -INF; for (int j = i; j <= n; j++) { dp[j] = max(dp[j - 1], maxv[j - 1]) + a[j]; maxv[j - 1] = temp; temp = max(temp, dp[j]); } } printf("%d\n", temp); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。