大师课T2 WA on test 9 求调

问题讨论区 提高段
1 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k,ans=0;
int a[3005][3005],dp[3005],tp[20][3005],t[3005];
void solve(int l,int r,int d){
	if(l==r){
		for(int i=0;i<=t[l];i++){
			ans=max(ans,a[l][i]+dp[k-i]);
		}
		return;
	}
	int mid=(l+r)/2;
	for(int i=0;i<=k;i++){
		tp[d][i]=dp[i];
	}
	for(int i=l;i<=mid;i++){
		for(int j=k;j>=t[i];j--){
			if(j>=t[i]&&j-t[i]<=k){
				dp[j]=max(dp[j],dp[j-t[i]]+a[i][t[i]]);
			}
		}
	}
	solve(mid+1,r,d+1);
	for(int i=0;i<=k;i++){
		dp[i]=tp[d][i];
	}
	for(int i=mid+1;i<=r;i++){
		for(int j=k;j>=t[i];j--){
			if(j>=t[i]&&j-t[i]<=k){
				dp[j]=max(dp[j],dp[j-t[i]]+a[i][t[i]]);
			}
		}
	}
	solve(l,mid,d+1);
	for(int i=0;i<=k;i++){
		dp[i]=tp[d][i];
	}
}
signed main(){
	int n;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		for(int j=1;j<=t[i];j++){
			if(j<=k){
				cin>>a[i][j];
				a[i][j]+=a[i][j-1];
			}else{
				break;
			}
			if(t[i]>k){
				t[i]=k;
			}
		}
	}
	solve(1,n,0);
	cout<<ans;
}

image

2

@吴梓峤 @charlieqi @王峥睿

3

这个不能放在这里，要放内循环外面，不然内循环次数会有问题

4

还有你这里输入次数会有问题

5

TLE 了。。。

6

代码

7 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int k,ans=0;
int a[3005][3005],dp[3005],tp[20][3005],t[3005];
void solve(int l,int r,int d){
	if(l==r){
		for(int i=0;i<=t[l];i++){
			ans=max(ans,a[l][i]+dp[k-i]);
		}
		return;
	}
	int mid=(l+r)/2;
	for(int i=0;i<=k;i++){
		tp[d][i]=dp[i];
	}
	for(int i=l;i<=mid;i++){
		for(int j=k;j>=t[i];j--){
			if(j>=t[i]&&j-t[i]<=k){
				dp[j]=max(dp[j],dp[j-t[i]]+a[i][t[i]]);
			}
		}
	}
	solve(mid+1,r,d+1);
	for(int i=0;i<=k;i++){
		dp[i]=tp[d][i];
	}
	for(int i=mid+1;i<=r;i++){
		for(int j=k;j>=t[i];j--){
			if(j>=t[i]&&j-t[i]<=k){
				dp[j]=max(dp[j],dp[j-t[i]]+a[i][t[i]]);
			}
		}
	}
	solve(l,mid,d+1);
	for(int i=0;i<=k;i++){
		dp[i]=tp[d][i];
	}
}
signed main(){
	
	int n;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		for(int j=1;j<=t[i];j++){
			if(j<=k){
				cin>>a[i][j];
				a[i][j]+=a[i][j-1];
			}else{
				for(int p=j;p<=t[i];p++){
					int x;
					cin>>x;
				}
				break;
			}
		}
		if(t[i]>k){
			t[i]=k;
		}
	}
	solve(1,n,0);
	cout<<ans;
}
8

稍等，我需要点时间看看

9

我的意思是说，你的a[i][j]输入不要放在if内，拿出来就好了

10

AC了，加个

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

就行

1 个赞
11

@LeuR 关帖！