P1063 能量项链(区间dp经典题)
程序员文章站
2024-02-24 22:26:10
...
https://www.luogu.org/problemnew/show/P1063
题解
这个和合并石子的不同之处就是一个珠子多了头和尾的能量,并可以成环,成环的解决方法便是复制一遍即可,合并的时候就要有一些细节处理。比较简单的方法就是把长度为3的区间当成是两个珠子合并的结果,那么n个珠子合并便是长度为n+1的区间。
为什么这样呢,因为珠子1与珠子2合并的能量是 珠子1珠子2珠子3
转移方程:
dp[l][r] = max(dp[l][r], dp[l][k]+dp[k][r]+a[l]*a[k]*a[r])。
代码
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> pii;
typedef long long ll;
const int maxn = 200+10;
int n;
pii a[maxn];
int dp[maxn][maxn];
int main() {
scanf("%d", &n);
for(int i = 0; i < n; ++i) {
scanf("%d", &a[i].x);
a[i+n].x = a[i].x;
}
for(int i = 0; i < n; ++i) {
a[i].y = a[(i+1)%n].x;
a[i+n].y = a[i].y;
}
int len = (n<<1);
for(int i = 0; i < len; ++i) dp[i][i] = 0;
int ans = 0;
for(int i = 2; i <= n+1; ++i) { // 因为成环,所以是n+1,[1,3] 相当于[1,2]的值
for(int l = 0; l+i-1 <= len-1; ++l) {
int r = l+i-1;
int v = dp[l][r];
for(int k = l+1; k < r; ++k) {
// cout << r << endl;
// << "#" << l << " " << k << " " << r << endl;
// cout << a[j].x << " " << a[k].y << " " << a[r].y << endl;
v = max(v, dp[l][k]+dp[k][r]+a[l].x*a[k].x*a[r].x);
// cout << j << " " << r << " " << dp[j][r] << endl;
// cout << v << endl;
}
dp[l][r] = v;
ans = max(v,ans);
}
}
cout << ans << endl;
return 0;
}
推荐阅读