搜索
您的当前位置:首页正文

【刷题】动态规划——区间DP:石子合并(NOI1995)【环形区间DP】

来源:独旅网

在基础上新加了可以合并开头和结尾俩堆石子。

以样例为例,最小得分的方案:
1、合并4 4 -> 8,得分8
2、合并8 5 -> 13,得分13
3、合并13 9 -> 22,得分22
总得分8 + 13 + 22 = 43

朴素想法:每合并1次用边将俩石子相连,因为长为n,所以合并n-1次,而n的环相邻可连n条边,总有俩石子之间没有边(样例就是5和9之间),枚举这个的位置,将其拆成链,用之前的做法得到答案。这样时间复杂度是O(n4),会超时。


对于环的常用方法,是将环拆成链再复制一遍接在后面,变成长度为2n-1的链
例如,1 2 3 4可以变成1 2 3 4 1 2 3,对这个链任取长度为n的区间,和在环上取区间等价。

#include <iostream> 
#include <cstring>
using namespace std;
int n, a[305], sum[605], f[605][605], g[605][605];
int main() {
	scanf("%d", &n);
	memset(f, 0x3f, sizeof(f));
	//memset(g, -0x3f, sizeof(g));
	for (int i = 1; i <= n; i ++ ) {
		scanf("%d", &a[i]);
		
	}
	for (int i = 1; i < 2 * n; i ++ ) {
		f[i][i] = 0;
		g[i][i] = 0;
		sum[i] += sum[i - 1] + a[(i - 1) % n + 1];
	}	
	for (int l = 2; l <= n; l ++ ) {
		for (int i = 1; i + l - 1 < 2 * n; i ++ ) {
			int j = i + l - 1;
			for (int k = i; k < j; k ++ ) {
				f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + sum[j] - sum[i - 1]);
				g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + sum[j] - sum[i - 1]);
			}
		}
	}
	int min_ans = 0x3f3f3f3f;
	int max_ans = -0x3f3f3f3f; 
	for (int i = 1; i <= n; i ++ ) {
		min_ans = min(min_ans, f[i][i + n - 1]);
		max_ans = max(max_ans, g[i][i + n - 1]);
	}
	printf("%d\n%d\n", min_ans, max_ans);
	return 0;
}

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top