题解：P1063 [NOIP2006 提高组] 能量项链

· · 题解

这道题就是区间动态规划的一道超级~水~模版的一道题。与这道题几乎一模一样。

思路：

  1. 区间动态规划数组定义：就简单粗暴， dp_{i,j} 表示区间 [i，j) 中最大能量释放值。注意，区间是左闭右开。

  2. 确定区间分段。没有特殊限制，时间复杂度允许。 循环 k （区间 [i,j) , i<k<j ）。

  3. 状态转移方程。已知区间 [i,j) ，断点 k 。求 dp[i][j] 。 首先， dp_{i,k} 与 dp_{k,j} 合并。最后再加上断点左右的区间最大能量释放值就行了，即 dp_{i,k} 与 dp_{k,j} 的和。 由题意，有以下计算代码：

int yh(int m,int r,int n){
    return m*r*n;
}//r,断点。m,区间[i,j)的i。n,区间[i.j)的j。

完整代码：

#include<bits/stdc++.h>
#define int long long
#include<iostream>
#define unsigned long long ull
using namespace std;
int yh(int m,int r,int n){
    return m*r*n;
}
const int N=210;
int a[N];
int dp[N][N];
int n;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i+n]=a[i];//环形，数组按照a[1]，……，a[n],a[1],……,a[n]存
    }
    n*=2;//环形，长度乘2。
    for(int len=2;len<=n;len++){//当前序列长度
        for(int i=1;i<=n-len+1;i++){//当前序列开头
            int j=i+len-1;//当前序列结尾
            for(int k=i+1;k<j;k++){//枚举断点
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+yh(a[i],a[k],a[j]));//状态转移
            }
        }
    }
    cout<<dp[1][n]/2;//n乘了2的，要除回去，或者循环在1~n,2~n+1,3~n+2……里面找最大值
    return 0;
}