caioj 1074 动态规划入门（中链式1：最小交换合并问题）

经典的石子合并问题！！！

设f[i][j]为从i到j的最大值

然后我们先枚举区间大小，然后枚举起点终点来更新

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

最后f[1][n]就是答案！！

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 212;

int f[MAXN][MAXN], a[MAXN], s[MAXN], n;

int main()

{

	int ans = 1e9;

	scanf("%d", &n);

	REP(i, 1, n + 1) scanf("%d", &a[i]);

	REP(r, 1, n)

	{

		swap(a[r], a[r + 1]);

		REP(i, 1, n + 1) s[i] = s[i-1] + a[i];

		swap(a[r], a[r + 1]);

		REP(d, 2, n + 1)

			for(int st = 1; st + d - 1 <= n; st++)

			{

				int i = st, j = st + d - 1;

				f[i][j] = 1e9;

				REP(k, i, j)

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

			}

		ans = min(ans, f[1][n]);

	}

	printf("%d\n", ans);

	return 0;

}

巴特西

caioj 1074 动态规划入门（中链式1：最小交换合并问题）

最新文章

热门文章