碎碎念
- 听完老师的讲课，对区间DP理解深入多了，继续刷题！
题目：[NOIP2006 提高组] 能量项链
题目原文请移步下面的链接
- https://www.luogu.com.cn/problem/P1063
- 参考题解：https://www.luogu.com.cn/problem/solution/P1063
- 标签：
OI、dp、区间 dp
题解
思路
- 区间dp，因为是环形所以要先转成链形，可以首尾相加取余n也可以直接用二倍算，是个小技巧。
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int m = 305;
const int INF = 0x3f3f3f3f;
int main () {
int n;
cin >> n;
vector<vector<int>> dp(m, vector<int>(m));
vector<int> s(2 * m);
for (int i = 1; i <= n; i) {
scanf("%d", &s[i]);
s[i n] = s[i];
}
for (int i = 2; i <= n 1; i) {
for (int j = 1; j i - 1 <= 2 * n; j) {
int z = j i - 1;
for (int k = j 1; k <= z - 1; k) {
dp[j][z] = max(dp[j][z], dp[j][k] dp[k][z] s[z] * s[j] * s[k]);
}
}
}
int ans = 0;
for(int i = 1; i <= n; i) {
ans = max(ans, dp[i][i n]);
}
cout << ans;
return 0;
}
