洛谷 P1281 书的复制

书的复制

---

Code：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//Mystery_Sky
//
#define M 700
#define INF 0x3f3f3f3f
int f[M][M], sum[M], a[M];
int n, k;

void print(int r)
{
	int num = 0;
	for(int i = r; i >= 1; i--) {
		num += a[i];
		if(num > f[n][k]) {
			print(i);
			printf("%d %d
", i+1, r);
			break;
		}
		if(i == 1) {
			printf("%d %d
", i, r);
			return;
		}
	}
	return;
}

int main() {
	scanf("%d%d", &n, &k);
	memset(f, INF, sizeof(f));
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		sum[i] = sum[i-1] + a[i];
		f[i][1] = sum[i];
	}
	for(int j = 2; j <= k; j++) {
		for(int i = j; i <= n; i++) {
			for(int l = j; l <= i; l++) {
				f[i][j] = min(f[i][j], max(f[l-1][j-1], sum[i] - sum[l-1]));
			}
		}
	}
	print(n);
	return 0;
}