题目概述
一共有n件食材，每件食材有三个属性，ai，bi和ci，如果在t时刻完成第i样食材则得到ai-t*bi的美味指数，用第i件食材做饭要花去ci的时间。设计烹调方案使得美味指数最大。
对于40%的数据1<=n<=10
对于100%的数据1<=n<=50
所有数字均小于100,000
解题思路
这是一道01背包问题，但选择顺序对结果有影响。对于任意两件食材i和j，若i在j前面，则损失的美味指数为b[i]*c[i]+b[j]*(c[i]+c[j]);若j在i前，则损失的美味指数为b[j]*c[j]+b[i]*(c[i]+c[j])。由于美味指数只会随时间而减小，那么我们需要使损失的美味指数尽可能小：按b[i]*c[j]由小到大排序。
f[i,j]表示前i件
时间复杂度:O(nt)
空间复杂度:O(nt)
源程序
var
a,b,c:array[0..50]of longint;
d,f:array[0..100000]of int64;
i,j,n,m,t:longint;
ans:int64;
function max(a,b:int64):int64;
begin
if a>b then exit(a)
else exit(b);
end;
begin
readln(t,n);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to n do
read(b[i]);
readln;
for i:=1 to n do
read(c[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if b[i]*c[j]>b[j]*c[i] then
begin
a[0]:=a[i];
a[i]:=a[j];
a[j]:=a[0];
b[0]:=b[i];
b[i]:=b[j];
b[j]:=b[0];
c[0]:=c[i];
c[i]:=c[j];
c[j]:=c[0];
end;
for i:=1 to n do
begin
d:=f;
fillchar(f,sizeof(f),0);
for j:=0 to t-c[i] do
f[j]:=max(d[j],d[j+c[i]]+a[i]-(t-j)*b[i]);
if t-c[i]>0 then
for j:=t-c[i]+1 to t do
f[j]:=d[j];
end;
ans:=0;
for i:=0 to t do
if ans<f[i] then ans:=f[i];
write(ans);
end.