T2Time limit exceeded on test 10谁能解释一下正解为什么TLE

问题讨论区 提高段
1

捕获

#include<bits/stdc++.h>
using namespace std;
long long n,k,dp[3010][3010],ans;
long long a[3010][3010];
void solve(int l,int r,int d)
{
	if(l==r)
	{
		ans=max(ans,dp[d][k]);
		for(int i=1;i<=min(k,a[l][0]);i++)
		{
			ans=max(ans,dp[d][k-i]+a[l][i]);
		}
		return;
	}
	int mid=l+r>>1;
	for(int i=mid+1,ii=d+1;i<=r;i++,ii++)
	{
		for(int j=1;j<=k;j++)
		{
			dp[ii][j]=dp[ii-1][j];
			if(j>=a[i][0])
			dp[ii][j]=max(dp[ii][j],dp[ii-1][j-a[i][0]]+a[i][a[i][0]]);
		}
	}
	solve(l,mid,d+r-mid);
	for(int i=l,ii=d+1;i<=mid;i++,ii++)
	{
		for(int j=1;j<=k;j++)
		{
			dp[ii][j]=dp[ii-1][j];
			if(j>=a[i][0])
			dp[ii][j]=max(dp[ii][j],dp[ii-1][j-a[i][0]]+a[i][a[i][0]]);
		}
	}
	solve(mid+1,r,d+mid-l+1);
	return;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		long long x;
		cin>>a[i][0];
		for(int j=1;j<=a[i][0];j++)
		{
			cin>>x;
			if(j>k)
			{
				continue;
			}
			a[i][j]=x;
			if(j!=1)
			{
				a[i][j]+=a[i][j-1];
			}
		}
	}
	for(int i=1;i<=k;i++)
	{
		dp[0][i]=-1e18;
	}
	solve(1,n,0);
	cout<<ans;
}
2

关输入输出流试试

1 个赞
3

我不会这些duliu小技巧，教教

1 个赞
4 
int main()
{
    ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
    cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		long long x;
		cin>>a[i][0];
		for(int j=1;j<=a[i][0];j++)
		{
			cin>>x;
			if(j>k)
			{
				continue;
			}
			a[i][j]=x;
			if(j!=1)
			{
				a[i][j]+=a[i][j-1];
			}
		}
	}
	for(int i=1;i<=k;i++)
	{
		dp[0][i]=-1e18;
	}
	solve(1,n,0);
	cout<<ans;
}

改成这样

1 个赞
5

用快读（我不会 自己查吧）
或者用ios::sync_with_stdio(0);cin.tie(0);

1 个赞
6

你这解决方案拿得有点水
image

1 个赞