萌新入门分治求助,给关注,谢谢
  • 板块CF1442D Sum
  • 楼主Wsyflying2022
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/3/17 06:03
  • 上次更新2023/10/28 06:25:14
查看原帖
萌新入门分治求助,给关注,谢谢
97737
Wsyflying2022楼主2022/3/17 06:03
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
typedef long long LL;
int n,k;
vector <int> a[maxn];
LL ans,sum[maxn],tmp[maxn],f[maxn];
int len[maxn];
inline void dfs(int l,int r) {
	if (l==r) {
		LL tsum=0;
		ans=max(ans,f[k]);
		for (int i=1;i<=len[l];i++) {
			tsum+=a[l][i-1];
		    if (k>=i) ans=max(ans,f[k-i]+tsum);
		      else break;
		}
		return ;
	}
	int mid=(l+r)>>1;
	for (int i=0;i<=k;i++) tmp[i]=f[i];
	for (int i=mid+1;i<=r;i++) {
		for (int j=k;j>=len[i];j--)
		  f[j]=max(f[j],f[j-len[i]]+sum[i]);
	}
	dfs(l,mid);
	for (int i=0;i<=k;i++) f[i]=tmp[i];
	for (int i=l;i<=mid;i++) {
		for (int j=k;j>=len[i];j--)
		  f[j]=max(f[j],f[j-len[i]]+sum[i]);
	}
	dfs(mid+1,r);
}
int main() {
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++) {
		scanf("%d",&len[i]);
		for (int j=1;j<=len[i];j++) {
			int x;
			scanf("%d",&x);
			sum[i]+=x;
			a[i].push_back(x);
		}
	}
	dfs(1,n);
	printf("%lld\n",ans);
	return 0;
} 
2022/3/17 06:03
加载中...