Think: 1知识点：基础dp 2题意：n个数分成m部分的最大值
二维表示
dp[i][j]:j个数分成i部分的最大值 状态转移方程 dp[i][j] = max(dp[i][j-1]+a[j], max(dp[i-1][k])+a[j]), 0<k<j一维优化
dp[j]数组表示前j个数分成当前i部分的最大值 mav[j]数组表示第j层的最大值 状态转移方程 dp[j] = max(dp[j-1]+a[j], mav[j-1]+a[j]);vjudge题目链接
建议参考博客1 建议参考博客2
以下为Accepted代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int inf = 0x3f3f3f3f; const int N = 1e6 + 4e2; int dp[N], a[N], mav[N]; /*1.dp[j]数组表示前j个数分成当前i部分的最大值*/ /*2.mav[j]数组表示第j层的最大值*/ int main(){ int m, n, i, j, mx; while(~scanf("%d %d", &m, &n)){ for(i = 1; i <= n; i++) scanf("%d", &a[i]); dp[0] = 0; memset(mav, 0, sizeof(mav)); for(i = 1; i <= m; i++){ mx = -inf; for(j = i; j <= n; j++){ dp[j] = max(dp[j-1]+a[j], mav[j-1]+a[j]); mav[j-1] = mx; mx = max(mx, dp[j]);/*更新记录分成i部分第j层的最大值*/ } } printf("%d\n", mx);/*输出分成m部分的最大值*/ } return 0; }