文章目录
- P1063 [NOIP2006 提高组] 能量项链
- AC代码
P1063 [NOIP2006 提高组] 能量项链
本题链接：P1063 [NOIP2006 提高组] 能量项链
本博客给出本题截图：
AC代码
代码解释：和题目 P1880 [NOI1995] 石子合并 大意一致，相同的东西不再进行赘述，这里说一下细节上的区别，首先就是我们的len更新为最少长度为3，上一题中为1(当然可以是2)，这里的原因是和输入有关系，因为三组数据其实代表的是两个不同的石头，然后len的最大值为n + 1，这里的n + 1其实就是第一个石头的左端点，然后就是本题不需要进行前缀和处理，直接相乘即可，状态转移方程中，因为从k的位置分开，k这个位置上的值即代表[i, k]的右端点，又代表[k, j]的左端点，故为：
f[i][j] = max(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]);
最后一个不同的地方就是k的取值范围，为[i + 1, r)，因为两组数才表示一个点
代码：
#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 210; int w[N]; int f[N][N]; int main() { int n; cin >> n; for (int i = 1; i <= n; i ++ ) { cin >> w[i]; w[i + n] = w[i]; } for (int len = 3; len <= n + 1; len ++ ) for (int i = 1; i + len - 1 <= 2 * n; i ++ ) { int j = i + len - 1; for (int k = i + 1; k < j; k ++ ) f[i][j] = max(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]); } int res = 0; for (int i = 1; i <= n; i ++ ) res = max(res, f[i][i + n]); cout << res << endl; return 0; }
