Codeforces 148E 【DP】
Разница между en5 и en6, 27 символ(ов) изменены
先进行一遍DP,求出f[i][j]表示第i层取j本书的最大价值和,这个DP利用前缀和可以优化成  $O(N^{3})$  。↵
然后再进行一遍DP,求出g[i][j]表示前i层取j本书的最大价值和,这个DP也是  $O(N^{3})$  的。↵

~~~~~↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<cmath>↵
#include<algorithm>↵
#include<vector>↵
using namespace std;↵
inline int read()↵
{↵
int x=0,f=1; char ch=getchar();↵
while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}↵
while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}↵
return x*f;↵
}↵
#define size(i) s[i].size()-1↵
vector<int>s[110],sum[110];↵
int f[110][10010],g[110][10010],N,M;↵
int main()↵
{↵
for (int i=1; i<=100; i++) s[i].push_back(0),sum[i].push_back(0);↵
N=read(),M=read();↵
for (int x,i=1,len,j; i<=N; i++) ↵
for (len=read(),j=1; j<=len; j++)↵
x=read(),s[i].push_back(x),sum[i].push_back(sum[i][j-1]+s[i][j]);↵
for (int i=1; i<=N; i++)↵
for (int j=1; j<=size(i); j++)↵
for (int k=1; k+size(i)-j-1<=size(i); k++)↵
f[i][j]=max(f[i][j],sum[i][size(i)]-(sum[i][k+size(i)-j-1]-sum[i][k-1]));↵
// for (int i=1; i<=N; i++,puts(""))↵
// for (int j=1; j<=size(i); j++)↵
// printf("%d  ",f[i][j]);↵
for (int i=1,j,len=0; i<=N; i++)↵
for (len+=size(i),j=1; j<=len; j++)↵
for (int k=0; k<=size(i); k++)↵
if (j>=k && len-(size(i))>=j-k)↵
g[i][j]=max(g[i][j],g[i-1][j-k]+f[i][k]);↵
// for (int i=1; i<=N; i++,puts(""))↵
// for (int j=1; j<=size(i); j++)↵
// printf("%d  ",g[i][j]);↵
printf("%d\n",g[N][M]);↵
return 0;↵
}↵
~~~~~

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский LAGBOYDaD3zZ 2016-10-19 13:08:50 27
en5 Английский LAGBOYDaD3zZ 2016-10-19 13:08:28 0 (published)
en4 Английский LAGBOYDaD3zZ 2016-10-17 15:35:39 8
en3 Английский LAGBOYDaD3zZ 2016-10-17 15:35:24 26
en2 Английский LAGBOYDaD3zZ 2016-10-17 15:33:14 12
en1 Английский LAGBOYDaD3zZ 2016-10-17 15:32:14 1456 Initial revision (saved to drafts)