题目概述
一共有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.
