\(\text{Solution}\)

首先看这个数据范围和个数总和为 \(k\) 的限制都很像背包吧。

把每个数组拆成长度为 \([1,k]\) 的前缀再做背包显然在时间和正确性上都不可取（不好控制每个数组只选一个）。

我们都陷入怪圈。

感觉很多这种题都有一个结论来限制时间。比如这题：数组是不降的。

有一个结论：最多只有一个数组选了但是没有选完。

考虑有 \(i,j\) 两个数组分别选到第 \(p_i,p_j\) 的数。如果 \(a_{i,p_i}\le a_{j,p_j}\)，又因为有 \(a_{j,p_j}\le a_{j,p_{j+1}}\)，那么舍 \(p_i\) 而取 \(p_{j+1}\) 也，而且新的数组肯定也有 \(a_{i,p_i}\le a_{j,p_j}\)，差距还会更大。那显然两个数组如果都选了没有选完，可以削弱其中一个，不停选另一个知道某个数组全部选或全选为止。

考虑枚举那个选了没选完的数组，将其他数组抽象成一件物品，可以分别进行背包，时间复杂度 \(\mathcal O(n^2\times k)\)。

如何优化？每次选一个数组都跑其它数组其实有很多重复，我们可以进行分治来优化。时间复杂度 \(\mathcal O(n\times k\times \log n)\)。

详见代码。

\(\text{Code}\)

#include <cstdio>
#define rep(i,_l,_r) for(signed i=(_l),_end=(_r);i<=_end;++i)
#define print(x,y) write(x),putchar(y)

template <class T> inline T read(const T sample) {
	T x=0; int f=1; char s;
	while((s=getchar())>‘9‘||s<‘0‘) if(s==‘-‘) f=-1;
	while(s>=‘0‘&&s<=‘9‘) x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return x*f; 
} 

template <class T> inline void write(T x) {
	if(x<0) return (void)(putchar(‘-‘),write(-x));
	if(x>9) write(x/10);
	putchar(x%10^48);
}

#include <iostream>
using namespace std;

typedef long long ll;

const int maxn=3005;

int n,k,w[maxn][maxn];
ll val[maxn],ans,tmp,f[maxn];

void DP(int l,int r) {
	if(l==r) { // 每个数组都会被选中成为选了但是没有选完的数组
		tmp=0;
		rep(i,1,w[l][0]) {
			tmp+=w[l][i];
			ans=max(ans,f[k-i]+tmp);
		}
		return;
	}
	int mid=l+r>>1;	ll t[maxn];
	rep(i,0,k) t[i]=f[i];
	rep(i,l,mid) for(int j=k;j>=w[i][0];--j) f[j]=max(f[j],f[j-w[i][0]]+val[i]);
	DP(mid+1,r); // 保证那个数组在 [mid+1,r]，那么 [l,mid] 就可以全部抽象成意见物品背包，这样就不用选中 [mid+1,r] 的每个数都做一次 [l,mid] 的背包
	rep(i,0,k) f[i]=t[i];
	rep(i,mid+1,r) for(int j=k;j>=w[i][0];--j) f[j]=max(f[j],f[j-w[i][0]]+val[i]);
	DP(l,mid);
}

int main() {
	int y;
	n=read(9),k=read(9);
	rep(i,1,n) {
		w[i][0]=read(9);
		rep(j,1,w[i][0]) {
			y=read(9);
			if(j<=k) w[i][j]=y,val[i]+=w[i][j];
		}
		w[i][0]=min(w[i][0],k);
	}
	DP(1,n);
	print(ans,‘\n‘);
	return 0;
}

CodeForces - 1442D Sum

原文：https://www.cnblogs.com/AWhiteWall/p/14078847.html