#include <iostream>
using namespace std;
const int maxn=105, maxm=2505, con=-1000000000;
struct data
{
int t,h,e;
};
data a[maxn];
int dp[maxn][maxm];
int n,d,m;
void qsort(int m, int n)
{
int i=m, j=n, k=a[(m+n) /2].t;
do
{
while (a[i].t<k) i++;
while (a[j].t>k) j--;
if (i<=j)
{
data c=a[i]; a[i]=a[j]; a[j]=c;
i++; j--;
}
}while (i<=j);
if (m<j) qsort(m,j);
if (i<n) qsort(i,n);
}
int main()
{
scanf("%d%d",&d,&n);
for (int i=1; i<=n; i++)
scanf("%d%d%d",&a[i].t,&a[i].e,&a[i].h);
qsort(1,n);
a[0].t=0;
m=0;
for (int i=1; i<=n; i++)
m += a[i].h;
for (int i=0 ; i<=n ; i++)
for (int j=0; j<=m; j++)
dp[i][j]=con;
dp[0][0]=10;
for (int i=1; i<=n; i++)
{
if (a[i].t<=0) continue;
for (int j=0; j<=d; j++)
{
if (dp[i-1][j]<a[i].t) continue;
dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].e);
int t= j+a[i].h;
if (t>=d)
{
printf("%d\n",a[i].t);
system("pause");
return 0;
}
dp[i][t]=max(dp[i][t],dp[i-1][j]);
}
if (dp[i][0]<0)
{
printf("%d\n",dp[i-1][0]);
system("pause");
return 0;
}
}
}
测试结果1: 通过本测试点|有效耗时62ms
测试结果2: 测试结果错误.错误结果为:13
正确结果应为:132
测试结果3: 通过本测试点|有效耗时47ms
测试结果4: 测试结果错误.错误结果为:109
正确结果应为:209
测试结果5: 通过本测试点|有效耗时47ms
测试结果6: 测试结果错误.错误结果为:510
正确结果应为:615
测试结果7: 测试结果错误.错误结果为:510
正确结果应为:2980
测试结果8: 通过本测试点|有效耗时47ms
测试结果9: 测试结果错误.错误结果为:45
正确结果应为:203
测试结果10: 通过本测试点|有效耗时46ms
const
maxd=125;
maxh=4010;
var
d,g:integer;
t,f,h:array[1..100]of integer;
a :array[0..maxd,1..maxh]of boolean;
procedure swap(var a,b:integer);
var c:integer;
begin
c:=a;a:=b;b:=c;
end;
procedure init;
var k,i,j:integer;
begin
readln(d,g);
for k:=1 to g do readln(t[k],f[k],h[k]);
for i:=1 to g-1 do
for j:=i+1 to g do
if t[i]>t[j] then
begin
swap(t[i],t[j]);
swap(f[i],f[j]);
swap(h[i],h[j]);
end;
end;
procedure main;
var
k,i,j,mh:integer;
begin
mh:=0;
for i:=1 to g do if t[i]>mh then mh:=t[i];
inc(mh,10);
for i:=1 to g do inc(mh,f[i]);
fillchar(a,sizeof(a),0);
a[0,10]:=true;
for k:=1 to g do
for i:=d-1 downto 0 do
for j:=mh downto t[k] do
if a[i,j] then
begin
a[i+h[k]][j]:=true;
if (i+h[k]>=d) then
begin
writeln(t[k]);
exit;
end;
a[i][j+f[k]]:=true;
end;
for j:=mh downto 1 do if a[0,j] then
begin writeln(j); exit end;
end;
begin
assign(input,'well.in');
reset(input);
assign(output,'well.out');
rewrite(output);
init;
main;
close(input);
close(output);
end.