P1063 能量项链
本题（NOIP2006）和石子合并（NOI1999）几乎一模一样 垃圾NOIP抄袭NOI，手动狗头
但是还是有细微的区别的，首先你得先能看懂题，石子合并是N堆石子，是 i − k i-k i−k和 k + 1 − j k+1-j k+1−j之间的合并，但是本题能量项链，是i，j，k三个相邻的珠子起作用，得分是 a [ i ] ∗ a [ j ] ∗ a [ k ] a[i]*a[j]*a[k] a[i]∗a[j]∗a[k]三个相邻的珠子的值

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)
using namespace std;
typedef long long ll;//全用ll可能会MLE，ll比int占的内存大
const ll N=1002;
const ll INF=1e9+7;
const ll mod=2147483647;
const double EPS=1e-6;
ll n,m,a[N],f[N][N];
ll ans;
int main()
{
    scanf("%lld",&n);over(i,1,n)scanf("%lld",&a[i]),a[i+n]=a[i];
    over(p,1,n)for(int i=1,j=i+p;(j<=2*n);i++,j=i+p)over(k,i+1,j-1)
    f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
    over(i,1,n)ans=max(f[i][i+n],ans);printf("%lld\n",ans);
}
    /*疯狂压行，只需要4行代码就可以ACNOIP！（大雾）*/
/* int main() { scanf("%lld",&n); over(i,1,n) { scanf("%lld",&a[i]); a[i+n]=a[i]; } over(p,1,n) { for(int i=1,j=i+p;(j<=2*n);i++,j=i+p) { over(k,i+1,j-1) { f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]); } } } over(i,1,n)ans=max(f[i][i+n],ans); printf("%lld\n",ans); return 0; } */

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧