进来DP

大部分代码贪心解法是错误的,原题是CF1442D,可以在cf上测试一下.

首先不考虑贪心,这是个分组背包$O(N^{2}K)O(N^2K)$,考虑贪心暴力仍然是$O(N^{2}K)O(N^2K)$.

贪心题解讲的很清楚了,那么我们如何能够做到更优的时间复杂度解决这个问题呢.

可以是分治,在每次递归到某个叶子节点的时候提前把n-1个序列全取了就ok啦.这就看你如何写分治了.

定义solve(l,r)为更新了[1,l-1],[r+1,n]的dp值,现在解决[l,r]区段.

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3005;
const int mod=1e9+7;
ll dp[N],sum[N],ans=0;
int n,k,c[N];
vector<int>a[N];
void solve(int l,int r)
{
	if(l==r)
	{
		ll res=0;
		for(int i=1;i<=min(c[l],k);i++)
		{
			res=res+a[l][i];
			ans=max(ans,res+dp[k-i]);
		}
		return;
	}
	int mid=(l+r)>>1;
	ll f[N];
	for(int i=0;i<=k;i++)	f[i]=dp[i];
	for(int i=mid+1;i<=r;i++)
	{
		for(int j=k;j>=c[i];j--)
		{
			dp[j]=max(dp[j],dp[j-c[i]]+sum[i]);
		}
	}
	solve(l,mid);
	for(int i=0;i<=k;i++)	dp[i]=f[i];
	for(int i=l;i<=mid;i++)
	{
		for(int j=k;j>=c[i];j--)
		{
			dp[j]=max(dp[j],dp[j-c[i]]+sum[i]);
		}
	}
	solve(mid+1,r);
}

void run()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&c[i]);
    	a[i].push_back(0);
    	for(int j=1;j<=c[i];j++)
    	{
    		int x;
    		scanf("%d",&x);
    		a[i].push_back(x);
    		sum[i]+=x;
		}
	}
	solve(1,n);
	printf("%lld\n",ans);
}

int main()
{
	int T=1;
	//cin>>T;
	while(T--)
	{
		run();
	}
	return 0;
}