HDU 1024 Max Sum Plus Plus
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1024
题目翻译
将一个长度为 N 的序列，分为 M 段，使得 M 段之和最大。
题解
这道题目没有说M的范围，于是我思索了好久。然而并不会做M很大的。
于是我们用F[i][j]表示当前分为 i 段，以 j 为结尾的最大和，然后F[i][j] = max(F[i][j-1] + num[j] , F[i-1][1~j] + num[j])
当然，这是可以优化到一维的，同理。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Maxn=1e6; int n, m; int num[Maxn + 5]; LL DP[Maxn + 5]; LL rat[Maxn + 5]; inline void solve(int T){ for (int i = 1; i <= n; ++i) scanf("%d", &num[i]); memset(DP, -127, sizeof(DP)); memset(rat, 0, sizeof(rat)); DP[0]=0; for (int i = 1; i <= m; i++){ for (int j = i; j <= n; j++){ DP[j] = max(DP[j-1] + num[j] , rat[j-1] + num[j]); } rat[i] = DP[i]; for (int j = i + 1; j <= n; j++) rat[j] = max(rat[j - 1], DP[j]); /*for (int j = 1; j <= n; j++) printf("%lld ", rat[j]); printf("\n"); for (int j = 1; j <= n; j++) printf("%lld ", DP[j]); printf("\n");*/ } long long Ans = -2100000000; for (int i = m; i <= n; i++) Ans = max(Ans, DP[i]); printf("%lld\n", Ans); } int main(){ while(scanf("%d%d", &m, &n) != EOF) solve(0); return 0; } |
原文链接：HDU 1024 Max Sum Plus Plus
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!