LuoguP2876 [USACO07JAN]解决问题Problem Solving （区间DP）（未完成）

#include "Head.cpp"

const int N = 307;

int f[N][N], a[N], b[N], sumA[N], sumB[N];
int main(){
FileOpen();

	int n, M;
	io >> M >> n;
	R(i,2,n + 1){
		io >> a[i] >> b[i];
		sumA[i] = sumA[i - 1] + a[i];
		sumB[i] = sumB[i - 1] + b[i];
	}
	Fill(f, 0x3f);
	f[1][1] = 1;
	
	R(i, 2, n + 1){
		R(j,2,i){
			R(k,1,j - 1){
				if(f[k][j - 1] != 0x3f3f3f3f && sumB[j - 1] - sumB[k - 1] <= M){
					if(M - (sumB[j - 1] - sumB[k - 1]) >= sumA[i] - sumA[j - 1])
						f[j][i] = Min(f[j][i], f[k][j - 1] + 1);
					else if(M >= sumA[i] - sumA[j - 1])
						f[j][i] = Min(f[j][i], f[k][j - 1] + 2);
				}
			}
		}
	}
	
	int ans = 0x3f3f3f3f;
	R(i,2,n + 1){
		if(sumB[n + 1] - sumB[i - 1] <= M){
			ans = Min(ans, f[i][n + 1] + 1);
		}
	}
	printf("%d", ans);
	
	return 0;
}