玄关,小数能过大数爆
  • 板块CF1442D Sum
  • 楼主F1NE
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/16 08:36
  • 上次更新2024/7/16 08:43:59
查看原帖
玄关,小数能过大数爆
1163927
F1NE楼主2024/7/16 08:36
#include<bits/stdc++.h>
#define getm int m=(s+t)>>1
#define tst for(int w=0;w<=K;w++)cout<<dp[w]<<' ';printf("s=%d,t=%d\n",s,t)
#define ll long long
using namespace std;
const int maxi=3e3+9;
int N,K,len[maxi];
ll ans=0,sum[maxi],a[maxi][maxi];
vector<ll> f(maxi);
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
void dping(int s,int t,vector<ll> &dp){
	for(int i=s;i<=t;i++){
		for(int j=K;j>=len[i];j--){
			dp[j]=max(dp[j],dp[j-len[i]]+sum[i]);//tst;
		}
	}
	return;
}
void dfs(int s,int t,vector<ll> dp){
//tst;
	if(s==t){
		for(int i=0;i<=min(K,len[s]);i++)
			ans=max(ans,dp[K-i]+a[s][i]);
		return;
	}
	getm;
	vector<ll> tmp1=dp,tmp2=dp;
	dping(m+1,t,tmp1);
	dping(s,m,tmp2);
	dfs(s,m,tmp1);
	dfs(m+1,t,tmp2);
	return;
}
signed main(){
	////输入部分 
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		scanf("%d",&len[i]);
		for(int j=1;j<=len[i];j++){
			scanf("%lld",&a[i][j]);
			a[i][j]+=a[i][j-1];
		}
		sum[i]=a[i][len[i]];
	}
	////线段树dp
	dfs(1,N,f);
	cout<<ans<<endl;
	return 0;
} 
2024/7/16 08:36
加载中...