Description：

请人来解决问题，必须按顺序解决，第一个月给 $a[i]$ 元，第二个月给 $b[i]$ 元，从第二个月开始每月获得 $m$ 元，问最少几个月可以解决全部问题。

$1\leqslant n\leqslant 300$

Solution：

还是利用那个把要求解的答案放到状态里的方法，设 $f[i][j]$ 表示到了解决了 $i$ 个问题，花了 $j$ 个月，第 $j+1$ 个月已经用的钱最小值为 $f[i][j]$ ，知道了状态之后问题就很好解决了，转移为 $f[i][k+1]=\min(sb[i]-sb[j](f[j][k]+sa[i]-sa[j]\leqslant m))$ ，最后找一个 $f[n][i]$ 不为零的最小的 $i$ 即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int m,n;

#define MAXN 310

int a[MAXN],b[MAXN];

int sa[MAXN],sb[MAXN];

int f[MAXN][MAXN << 1];

int main()

{

	scanf("%d%d",&m,&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&a[i],&b[i]);

		sa[i] = sa[i - 1] + a[i];

		sb[i] = sb[i - 1] + b[i];

	}

	memset(f,0x3f,sizeof(f));

	f[0][0] = 0;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 0;j <= i;++j)

		{

			for(int k = 0;k <= 2 * n;++k)

			{

				if(f[j][k] + sa[i] - sa[j] <= m && sb[i] - sb[j] <= m)

				{

					f[i][k + 1] = min(f[i][k + 1],sb[i] - sb[j]);

				}

			}

		}

	}

	for(int k = 1;k <= 2 * n;++k)

	{

		if(f[n][k] != 0x3f3f3f3f)

		{

			cout << k + 2 << endl;

			break;

		}

	}

	return 0;

}