考状态的dp

我的方法可能比较奇怪

设f[i,j]表示第i个月解决j个问题可以最多解决到第几个问题

容易知道，答案（月份）不会超过2n+1；

f[i,j]=max(f[i-1,k]+j) 

复杂度为O(n^3)

代码如下

1 var f:array[0..1000,0..500] of longint; 2     b,a,sa,sb:array[0..500] of longint; 3     p,y,q,i,j,k,n,m:longint; 4 function max(a,b:longint):longint; 5   begin 6     if a>b then exit(a) else exit(b); 7   end; 8  9 begin10   readln(m,n);11   for i:=1 to n do12   begin13     readln(b[i],a[i]);14     sa[i]:=sa[i-1]+a[i];15     sb[i]:=sb[i-1]+b[i];16   end;17   f[1,0]:=0;18   i:=1;19   while i<=2*n+1 do20   begin21     inc(i);22     f[i,0]:=f[i-1,0];23     for j:=1 to n do24     begin25       if f[i-1,j]=0 then break;26       f[i,0]:=max(f[i,0],f[i-1,j]);27     end;28     for j:=1 to n do29     begin30       for k:=0 to n do31       begin32         if (f[i-1,k]=0) and (k<>0) then break;    //后面的状态不存在，直接退33         p:=f[i-1,k];34         q:=f[i-1,k]+j;35         if q>n then continue;36         y:=f[i-1,k]-k;37         if (sb[q]-sb[p]+sa[p]-sa[y]<=m) and (sa[q]-sa[p]<=m) then          //判断是否够这个月花的38           f[i,j]:=max(f[i,j],f[i-1,k]+j);39       end;40       if f[i,j]>=n then41       begin42         writeln(i+1);    //注意付完款一定是下个月43         halt;44       end;45       if f[i,j]=0 then break;46     end;47   end;48 end.

话说代码有的地方可能写的比较冗杂……