CF148E Porcelain 题解

题意

分析

按层处理出来第 \(i\) 层扔 \(j\) 个物品价值和的最大值，记为 \(f_{i,j}\) ，记录每层价值的前缀和和后缀和，枚举左侧扔几个，右侧扔几个，打擂台取最大值即可，\(f_{i,l+r}=max \{ pre_{i,l}+suf_{i,k-r+1} \}\)。剩下的部分就是一个分组背包板子，枚举每一层扔几个和剩余的空间，直接 dp 即可，假设 \(i\) 为层数， \(j\) 为剩余空间， \(t\) 为第 \(i\) 层扔的个数，容易得到 \(dp_t=max \{ dp_{j-t}+f_{i,t} \}\) 。最后的答案就是 \(dp_m\) 。

代码

#include 
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int MAXN=107;
const int inf=2139062143;
inline void qread(){}template
inline void qread(T1 &a,T2&... b)
{
	register T1 x=0;register bool f=false;char ch=getchar();
	while(ch<'0') f|=(ch=='-'),ch=getchar();
	while(ch>='0') x=(x*10)+(ch^48),ch=getchar();
	x=(f?-x:x);a=x;qread(b...);
}
templateinline T1 qmax(const T1 &x,const T2 &y){return x>y?x:y;}
templateinline T1 qmin(const T1 &x,const T2 &y){return x=1;j--) suf[i][j]=suf[i][j+1]+a[i][j];
	}
	for(i=1;i<=n;i++)
		for(int l=0;l<=k[i];l++)
			for(int r=0;l+r<=k[i];r++)
				f[i][l+r]=qmax(f[i][l+r],pre[i][l]+suf[i][k[i]-r+1]);
	for(i=1;i<=n;i++)
	{
		for(j=m;j>=0;j--)
		{
			for(int t=1;t<=k[i];t++)
			{
				if(j