求助:思路应该没问题但是WA了,玄关
  • 板块CF1442D Sum
  • 楼主F1NE
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/15 21:12
  • 上次更新2024/7/15 21:38:59
查看原帖
求助:思路应该没问题但是WA了,玄关
1163927
F1NE楼主2024/7/15 21:12
#include<bits/stdc++.h>
#define getm int m=(s+t)>>1
#define tst for(int w=1;w<=K;w++)cout<<dp[w]<<' ';cout<<endl 
using namespace std;
const int maxi=3e3+9;
int N,K,ans=0,len[maxi],sum[maxi],a[maxi][maxi];
vector<int> f(maxi);
int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}
vector<int> dping(int l,int r,vector<int> dp){
	for(int i=l;i<=r;i++){
		for(int j=K;j>=len[i];j--){
			dp[j]=max(dp[j],dp[j-len[i]]+sum[i]);
		}
	}
	//tst;
	return dp;
}
void dfs(int s,int t,vector<int> 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;
	dfs(s,m,dping(m+1,t,dp));
	dfs(m+1,t,dping(s,m,dp));
	return;
}
int main(){
	////输入部分 
	cin>>N>>K;
	for(int i=1;i<=N;i++){
		scanf("%d",&len[i]);
		for(int j=1;j<=len[i];j++){
			scanf("%d",&a[i][j]);
			a[i][j]+=a[i][j-1];
		}
		sum[i]=a[i][N];
	}
	////线段树dp
	dfs(1,N,f);
	cout<<ans;
	return 0;
} 
2024/7/15 21:12
加载中...