题目描述

在你的帮助下，G调整好了石块和荷叶的位置。D和Z踩着石块过了池塘，却发现G不见了。
原来G被大Boss捉走了。
大Boss有一种很厉害的武器，叫做能量球，它是由许多能量珠合成的。大Boss的能量球刚好用完了，他捉来了G，让G为他制作能量球。
能量球的制作方式如下：
现在有一串能量珠，每次合并两个相邻的能量珠，得到的新能量珠的能量为两个能量珠能量之和。而最终得到的大能量球的能量为每次得到的新能量珠的能量总和。
G知道，大Boss制作能量球是为了对付D和Z，所以她会尽量使得她制作的能量球能量值尽量小。

输入

共2行。
第1行一个整数n（1≤n≤200），表示共n个能量珠。
第2行n个整数，表示一串能量珠，其中第1颗和最后一颗能量珠是相连接的。

输出

一个整数，表示最小能量值。

思路

剖分问题，和矩阵链相乘类似，但是会超时，所以我们就要用四边形不等式优化（http://blog.csdn.net/qq_33229466/article/details/51484265）但是我用O2水了过去。。。

#include 
#include 
using namespace std;
int r[10005],c[5000][5000],sum[10005];
int ans=10000000;
__attribute__((optimize("O2")))
int min(int x,int y)
{
  return x

正解

#include 
#include 
using namespace std;
int r[10005],c[5000][5000],sum[10005],s[1000][1000];
int ans=10000000;
__attribute__((optimize("O2")))
int min(int x,int y)
{
  return xmain()
{
 freopen("power.in", "r", stdin);
 freopen("power.out", "w", stdout);
  int n;
  scanf("%d",&n);
  for (int i=1;i<=n;i++)
  {
    scanf("%d",&r[i]);  
    sum[i]=sum[i-1]+r[i];      
    r[i+n]=r[i];
  }

  for (int l=1;l<=n;l++)
  {
    for (int i=1;i<=n;i++)
    {
      c[i][i]=0;
      s[i][i]=i;
    }
    for (int d=1;d<=n-1;d++)
      for (int i=1;i<=n-d;i++)
      {
        int j;
        j=i+d;
        c[i][j]=0xfffffff;
        int tmp=sum[j]-(i>0?sum[i-1]:0);
        for (int k=s[i][j-1];k<=s[i+1][j];k++)
        {
          if (c[i][j]>c[i][k]+c[k+1][j]+tmp)
          {
             c[i][j]=c[i][k]+c[k+1][j]+tmp;
             s[i][j]=k;
          }
        }
      } 
    ans=min(ans,c[1][n]);
    for (int i=1;i<=10000;i++)
    {   
      r[i]=r[i+1];
      sum[i]=sum[i-1]+r[i];
    }
  }
  printf("%d\n",ans);
  return 0;
}