P1063 [NOIP2006 提高组] 能量项链

题目描述：

思路：

区间dp

状态：

dp[i] [j]表示合并i到j得到的最大能量

转移方程：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}
ll qpow(ll a,ll n){ll ans=1,base=a%mod;while(n){if(n&1)ans=(ans*base)%mod;base=(base*base)%mod;n>>=1;}return ans;}
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int n;
int dp[205][205];
int tr[205];

int main(){
    n = IntRead();
    for(int i = 1; i <= n; ++i){
        tr[i] = IntRead();
        tr[i + n] = tr[i];
    }
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i <= n * 2; ++i){
            int j = i + len - 1;
            if(j > n * 2)break;
            for(int k = i; k < j; ++k){
                dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + tr[i] * tr[k + 1] * tr[j + 1]);
            }
        }
    }
    int ma = -1e9;
    for(int i = 1; i <= n; ++i)ma = max(ma, dp[i][i + n - 1]);
    cout<<ma<<endl;
    return 0;
}