2012年南海初中竞赛 剪草（jzoj）

2012年南海初中竞赛 剪草（jzoj）

题目：

作者思路：dp，dp，dp！！！
f[j,k]:=min(f[j-1,k]+a[j]+b[j]i,f[j-1,k-1]+b[j](i-k));
初值：f[j,0]:=f[j-1,0]+a[j]+b[j]*i;

代码：

var a,b:array[-1..51] of longint;f:array[-1..51,-1..51] of longint;i,j,k,n,t,h:longint;
function min(a,b:longint):longint;
beginif a>b then exit(b) else exit(a);
end;
beginread(n,h);for i:=1 to n do read(a[i]);for i:=1 to n do read(b[i]);for i:=1 to n-1 dofor j:=i+1 to n doif b[i]>b[j] thenbegint:=a[i]; a[i]:=a[j]; a[j]:=t;t:=b[i]; b[i]:=b[j]; b[j]:=t;end;for i:=0 to n dobeginfor j:=1 to n dofor k:=1 to i do f[j,k]:=maxlongint div 10;for j:=1 to n do f[j,0]:=f[j-1,0]+a[j]+b[j]*i;for j:=1 to n dofor k:=1 to i dof[j,k]:=min(f[j-1,k]+a[j]+b[j]*i,f[j-1,k-1]+b[j]*(i-k));if f[n,i]<=h thenbeginwrite(i);halt;end;end;write(-1);
end.