描述
【题解】
设f[i][j]表示前i个数字分成了j段的最大子段和。 则f[i][j] = max(f[i-1][j]+a[i] (第i个数字和第j段合在一起),f[k][j-1]+a[i] (第i个数字作为第j段的第一个数字,同时在j-1段的情况中找到和最大的那个)) 这样的时间复杂度是\(O(m*n^2)\)的,代码的写法在代码1中 接下来我们做一些优化。 首先把数组的第二维改成滚动数组。 然后令F[i][j]=max(f[1..i][j]); 这样在做第二层的转移的时候f[i][j]就能直接用F[i-1][j-1]做转移了 当然也不用非得再重开一个新的数组。 在f[i][j]做完转移之后把它改成前缀的最大值就行。(注意一定要做完转移之后再改变,因为f[i][j]在转移的时候用到了f[i-1][j]) 这样在做转移的时候就少掉了O(N)的一次枚举了 复杂度变成O(n*m)的了.详见代码2
【代码1】
#include <cstdio> #include <algorithm> using namespace std; const int N = 1e6; const int M = 30; int f[N+10][M+10],a[N+10]; int n,m; int main(){ while (~scanf("%d%d",&m,&n)){ for (int i = 1;i <=n;i++) scanf("%d",&a[i]); for(int l = 1;l <= m;l++){ for (int i = l;i <= n;i++){ if (i==l){ f[i][l] = f[i-1][l-1]+a[i]; }else{ f[i][l] = f[i-1][l]+a[i];//和第l段合并 //printf("%d ",f[i][l]); //自己独立成段 for (int k = l-1;k <= i-1;k++) f[i][l] = max(f[i][l],f[k][l-1]+a[i]); } } } int ans = f[m][m]; for (int i = m+1;i <= n;i++) ans = max(ans,f[i][m]); printf("%d\n",ans); } return 0; }【代码2】
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 1e6; const int M = 30; int f[N+10][2],a[N+10]; int n,m; int main(){ while (~scanf("%d%d",&m,&n)){ for (int i = 1;i <=n;i++) scanf("%d",&a[i]); memset(f,0,sizeof f); for(int l = 1;l <= m;l++){ for (int i = l;i <= n;i++){ if (i==l){ f[i][l&1] = f[i-1][(l-1)&1]+a[i]; }else{ f[i][l&1] = f[i-1][l&1]+a[i];//和第l段合并 //printf("%d ",f[i][l]); //自己独立成段 f[i][l&1] = max(f[i][l&1],f[i-1][(l-1)&1]+a[i]); } } for (int i = l+1;i <= n;i++) f[i][l&1] = max(f[i][l&1],f[i-1][l&1]); } printf("%d\n",f[n][m&1]); } return 0; }