题目描述:
给定一串序列x[],其中的每一个Xi看作看作一颗珠子,每个珠子包含两个参数,head和tail,前一颗的tail值是后一个的head值,珠子呈现环形(是一条项链),所以最后一颗的tail是第一个珠子的head.当tail遇到对应的head时会放出
Xi.head*Xi.tail*X++i.head,之后这两颗相邻的珠子会变成新的一颗Xp,它的参数为Xp.head=Xi.head,Xp.tail=X++i.tail,问整条项链合并到只剩下一颗时所能产生的最大能量.
题目链接:P1063
至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。
输出格式
一个正整数E(E≤2.1×(10)9)E(E≤2.1 \times (10)^9)E(E≤2.1×(10)9)，为一个最优聚合顺序所释放的总能量。
in:
4
2 3 5 10
out:
710
思路:区间dp,以小区间来作为最优子结构来计算大区间,整个题目的解法等价于找1~E中从哪一个最开始先合并,我们以dp[i][j]表示合并区间i到j的最优解,在i到j中选取k开始合并的状态转移方程为:dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i].h*a[j].t*a[i+k].t)
那么算法大体就定下来了O(n^3)的思路
#include <bits/stdc++.h>
using namespace std;
struct node//存珠子
{
int h;
int t;
} e[];
int n;
int dp[][];
int total;
int main()
{
cin>>n;
for(int i=; i<n; i++)
{
int x;
cin>>x;
if(i==)
{
int y;
cin>>y;
e[i].h=x;
e[i].t=y;
continue;
}
e[i].h=e[i-].t;
e[i].t=x;
if(i==n-)
{
e[n].h=e[n-].t;
e[n].t=e[].h;
}
}//输入,第一个和最后一个做了特判
for(int i=; i<n; i++)
e[i+n]=e[i];//这一步很关键,相当于拆环,把整段序列在往尾部接上一次,以达到环形
for(int i=; i<=n; i++)
for(int j=; j<*n-i; j++)
for(int k=j; k<i+j; k++)
dp[j][j+i]=max(dp[j][j+i],dp[j][k]+dp[k+][j+i]+e[j].h*e[k].t*e[i+j].t);
for(int i=;i<=n;i++)
total=max(total,dp[i][i+n-]);
cout<<total; return ;
}