caioj 1075 动态规划入门（中链式2：能量项链）（中链式dp总结）

我又总结了一种动归模型……

这道题和上一道题很类似，都是给一个序列，然后相邻的元素可以合并

然后合并后的元素可以再次合并

那么就可以用这两道题类似的方法解决

简单来说就是枚举区间，然后枚举断点

加上断点左右两边的值（按照题目，可能不是加），然后在按题目加上计算合并后总的序列的值

就这一道题而言f[i][j] = max(f[i][k] + f[k+1][j] + a[i] * a[(k+1)%n] * a[(j+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 = 112;

int f[MAXN][MAXN], a[MAXN], b[MAXN];

int main()

{

	int n;

	scanf("%d", &n);

	REP(i, 0, n) scanf("%d", &b[i]);

	int ans = 0;

	REP(r, 0, n)

	{

		memset(f, 0, sizeof(f));

		REP(i, 0, n) a[i] = b[(i+r) % n];

		REP(d, 2, n + 1)

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

		{

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

			REP(k, i, j)

			f[i][j] = max(f[i][j], f[i][k] + f[k+1][j] + a[i] * a[(k+1)%n] * a[(j+1)%n]);

		}

		ans = max(ans, f[0][n - 1]);

	}

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

	return 0;

}

巴特西

caioj 1075 动态规划入门（中链式2：能量项链）（中链式dp总结）

最新文章

热门文章