描述
育母蜘蛛在打钱时积攒了许多的小蜘蛛,于是,育母蜘蛛想开一个小蜘蛛的展览会…… 育母蜘蛛对她的每一个小蜘蛛都做了力量和敏捷的评价(小蜘蛛没有智力),每个小蜘蛛的力量和敏捷分别为ai和bi 育母蜘蛛要从她的小蜘蛛中挑出一部分来进行展览,使得所有ai和bi的总和最大。并且,为了显示小蜘蛛的全面发展,ai的总和与bi的总和分别不能小于0 现在,育母蜘蛛想知道,能达到的最大的所有ai与bi的总和是多少?
输入
第一行,一个数N 接下来N行,每行两个数ai和bi
输出
一个数,即最大的所有ai与bi的总和
样例输入
5
-5 7
8 –6
6 –3
2 1
-8 –5
样例输出
8
提示
N<=100
-1000<=ai,bi<=1000
【Solution】
一个线性的Dp,实际上我过的非常纠结…因为Memory还是很勉强,骗分性质的我开了50000,而非标准的100000,这个问题的解决其实可以借助滚动数组。
F数组可以用F[i,j]表示前i个小蜘蛛使取的ai之和为j所获得的最大Sigma(ai+bi)
F[i,j]←max{F[i-1,j-a[i]]+value[i]}注意推的时候一定要用扩展过的合理的状态去转移。
最后的解是max{F[n,j]}(j>=0,F[n,j]-j>=0)
另外初始化的时候也一定要注意,要把F赋程-∞,F[0,0]=0。
【Code】
1: Program BroodMother(input,output);2: var F:array[0..100,-10000..10000]of longint;3: a,b,value:array[1..100]of longint;4: up,down,i,n,j,ans:longint;5: Function max(a,b:longint):longint;6: begin
7: if a>b then exit(a) else exit(b);8: end;
9: begin
10: readln(n);11: for i:=1 to n do12: begin
13: readln(a[i],b[i]);14: value[i]:=a[i]+b[i];15: if a[i]>0 then inc(up,a[i]) else inc(down,a[i]);16: end;
17: for i:=0 to 100 do18: for j:=-10000 to 10000 do19: F[i,j]:=-19940805;20: F[0,0]:=0;21: for i:=1 to n do22: for j:=down to up do23: begin
24: if(j-a[i]<=up)and(j-a[i]>=down)and(F[i-1,j-a[i]]>-19940805)25: then F[i,j]:=max(F[i,j],F[i-1,j-a[i]]+value[i]);
26: F[i,j]:=max(F[i,j],F[i-1,j]);27: end;
28: ans:=-19940805;29: for i:=0 to up do30: if F[n,i]-i>=0 then31: if ans<F[n,i] then ans:=F[n,i];32: writeln(ans);33: end.