佳佳的魔法杖（mwand）

佳佳的魔法杖（mwand）

算法：DP
 
分析：本题很容易就看出DP的影子来，关键是如何DP，肿么DP。
     用f[i,j]表示在起始点不超过i，终止点不超过j的情况下的最大取值。因为不能包含，因此可以从f[i-1,j]或f[i,j-1]中的最大值转移而来。

     但是还可以由f[i-1,j-1]+s[j]-s[i-1]（lo<=s[j]-s[i-1]<=hi）转移而来，因此本题可以说是对LCS的一个变形，同样是就看你理解的是否深刻了。

program mwand;constmaxn=1000;varn,lo,hi:longint;s1,s2:array [0..maxn] of longint;f:array [0..axn] of int64;procedure init;vari:longint;beginreadln(n,lo,hi);for i:=1 to n do beginread(s1[i]);inc(s1[i],s1[i-1]);end; readln;for i:=1 to n dobeginread(s2[i]);inc(s2[i],s2[i-1]);end;end;function max(x,y:int64):int64;beginif x>y then exit(x) else exit(y);end;function can(x,y:longint):boolean;beginif (s1[y]-s1[x-1]>=lo) and (s1[y]-s1[x-1]<=hi) then exit(true) else exit(false);end;procedure main;vari,j:longint;beginfor i:=1 to n dobeginfor j:=i to n do beginf[i,j]:=max(f[i-1,j],f[i,j-1]);if can(i,j) then f[i,j]:=max(f[i,j],f[i-1,j-1]+s2[j]-s2[i-1]);end;end;end;beginassign(input,'mwand.in'); reset(input);assign(output,'mwand.out'); rewrite(output);init;main;writeln(f[n,n]);close(input); close(output);end.