WA on #10 #12 #13

可见 这里

源代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e3+510;
int n,m,dp[N][N];
struct Tash{int t,f,h;}a[N];
bool vis[N][N];

bool cmp(Tash x,Tash y)
{
	return x.t<y.t;
}

int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d%d%d",&a[i].t,&a[i].f,&a[i].h);
	}
	
	sort(a+1,a+n+1,cmp);
	vis[0][10]=1;
	int lif=10,maxt=10;
	for(int i=1;i<=n;++i)
	{
		lif-=a[i].t-a[i-1].t;
		if(lif<0) break;
		lif+=a[i].f;
		maxt+=a[i].f;
	}
	
	for(int i=1;i<=n;++i)
	{
		for(int j=1e3;j>=0;--j)
		{
			int k=(a[i].t-a[i-1].t);
			if(vis[i-1][j+k]==1)
			{
				dp[i][j]=max(dp[i][j],dp[i-1][j+k]+a[i].h);
				vis[i][j]=1;
				
				dp[i][j+a[i].f]=max(dp[i-1][j+k],dp[i-1][j+a[i].f]);
				vis[i][j+a[i].f]=1;
			}
			if(vis[i][j] && dp[i][j]>=m)
			{
				printf("%d",a[i].t);
				return 0;
			}
		}
	}
	printf("%d",maxt);
	return 0;
}