#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.