考状态的dp
我的方法可能比较奇怪
设f[i,j]表示第i个月解决j个问题可以最多解决到第几个问题
容易知道，答案（月份）不会超过2n+1；
f[i,j]=max(f[i-1,k]+j)
复杂度为O(n^3)
代码如下
var f:array[..,..] of longint;
b,a,sa,sb:array[..] of longint;
p,y,q,i,j,k,n,m:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; begin
readln(m,n);
for i:= to n do
begin
readln(b[i],a[i]);
sa[i]:=sa[i-]+a[i];
sb[i]:=sb[i-]+b[i];
end;
f[,]:=;
i:=;
while i<=*n+ do
begin
inc(i);
f[i,]:=f[i-,];
for j:= to n do
begin
if f[i-,j]= then break;
f[i,]:=max(f[i,],f[i-,j]);
end;
for j:= to n do
begin
for k:= to n do
begin
if (f[i-,k]=) and (k<>) then break; //后面的状态不存在，直接退
p:=f[i-,k];
q:=f[i-,k]+j;
if q>n then continue;
y:=f[i-,k]-k;
if (sb[q]-sb[p]+sa[p]-sa[y]<=m) and (sa[q]-sa[p]<=m) then //判断是否够这个月花的
f[i,j]:=max(f[i,j],f[i-,k]+j);
end;
if f[i,j]>=n then
begin
writeln(i+); //注意付完款一定是下个月
halt;
end;
if f[i,j]= then break;
end;
end;
end.
话说代码有的地方可能写的比较冗杂……