「题解」Codeforces 1442D Sum

要取的话一定是全取完，如果没取完一个数组 \(x\) 就去取另外一个数组 \(y\) 更优的话，那么把取 \(x\) 的机会用到取 \(y\) 上会更优，这样就变成取完 \(y\) 再取 \(x\)，依然满足结论。

那就变成选出一些数组，把它们全取了，然后再在一个数组里面选一个前缀。

那就把数组看成物品，问题变成经典问题问删除一个物品之后的最优化背包，这个分治解决，大概就是递归 \([l,r]\) 时，把 \([l,mid]\) 插入的背包中，然后递归求解 \([mid+1,r]\)，然后再返回插入前的状态，把 \([mid+1,r]\) 塞进去，递归求解 \([l,mid]\)．

复杂度就是 \(\mathcal{O}(nk\log n)\)．

#include
#include
#include
#include
#include
#define pb emplace_back
#define mp std::make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pairpii;
typedef std::pairpli;
typedef std::pairpll;
typedef std::vectorvi;
typedef std::vectorvll;
templateT cmax(T &x, T y){ return x=x>y?x:y; }
templateT cmin(T &x, T y){ return x=x
T &read(T &r){
	r=0;bool w=0;char ch=getchar();
	while(ch<'0'||ch>'9')w=ch=='-'?1:0,ch=getchar();
	while(ch>='0'&&ch<='9')r=r*10+(ch^48),ch=getchar();
	return r=w?-r:r;
}
template
void read(T1 &x, T2& ...y){ read(x); read(y...); }
const int N=3010;
int n,k;
ll ans,a[N][N];
void solve(int l,int r,vll g){
	if(l==r){
		cmax(ans,g[k]);
		for(int i=1;i<=min((int)a[l][0],k);i++)cmax(ans,a[l][i]+g[k-i]);
		return ;
	}
	vll f=g; int mid=(l+r)>>1;
	for(int i=mid+1;i<=r;i++){
		int w=a[i][0]; ll v=a[i][a[i][0]];
		for(int j=k;j>=w;j--)cmax(f[j],f[j-w]+v);
	}
	solve(l,mid,f);
	f=g;
	for(int i=l;i<=mid;i++){
		int w=a[i][0]; ll v=a[i][a[i][0]];
		for(int j=k;j>=w;j--)cmax(f[j],f[j-w]+v);
	}
	solve(mid+1,r,f);
}
signed main(){
	read(n,k);
	for(int i=1;i<=n;i++){
		read(a[i][0]);
		for(int j=1;j<=a[i][0];j++)read(a[i][j]),a[i][j]+=j==1?0:a[i][j-1];
	}
	solve(1,n,vll(k+1));
	cout << ans << '\n';
	return 0;
}