技术教程 LuoguP2876 [USACO07JAN]解决问题Problem Solving （区间DP）（未完成） 正文

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

2022-10-26,,

#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;

}

LuoguP2876 [USACO07JAN]解决问题Problem Solving （区间DP）（未完成）的相关教程结束。

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

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!