SSL_2863【石を合併する】

ごうせいし
タイトル
ある運動場にはN山の石がずらりと並んでいる.今、石を順番に積み上げます.毎回隣接する2つの石を選んで新しい山に統合するしかなく、新しい石の数をこの合併の得点として記録することを規定しています.N山の石を1山に統合した最小得点を計算するプログラムを設計してください.
入力
各データ群の第1行目は正の整数N(2<=N<=100)であり、以下のN行は、1行ごとに正の整数が10000未満であり、それぞれ第i堆石の個数(1<=i<=N)を表す.
しゅつりょく
各グループのデータに対して正の整数、すなわち最小スコアを出力する
Sample Input

7
13
7
8
16
21
4
18

Sample Output

239

解析
この問題は1行数で、毎回2つの石を合併して新しい石を得る得点は貪欲で使えない.全体の最適解は部分の最適解を代表するものではない.だから、DPを使って、部分の全体の最適解の分割から最適解法の再帰式を得ることがよく計画されている.ここでは2つの石が合併していることが考えられる.したがって,最終最適解は2つの局所最適解に全体的な和を加えて求められるに違いない.コードをつけて!
コード1

#include
#include
using namespace std;
long long n,a[101],b[101][101],s[101];
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)cin>>a[i];
    for(long long i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(long long i=n-1;i>=1;i--)//    
 {
  for(long long j=i+1;j<=n;j++)//    
  {
            b[i][j]=0x7f7f7f7f;
   for(long long k=i;k<=j-1;k++)b[i][j]=min(b[i][j],b[i][k]+b[k+1][j]+s[j]-s[i-1]);
  }
 }
    cout<<b[1][n];
    return 0;
}

コード2

#include
#include
using namespace std;
long long n,a[101],b[101][101],c[101];
int main()
{
    cin>>n;
    for(long long i=1;i<=n;i++)cin>>a[i];
    for(long long i=1;i<=n;i++)c[i]=c[i-1]+a[i];
    for(long long i=2;i<=n;i++)//    
 {
  for(long long j=1;j<=n-i+1;j++)//    
  {
   long long t=j+i-1;
            b[j][t]=0x7f7f7f7f;
   for(long long k=j;k<=t;k++)b[j][t]=min(b[j][t],b[j][k]+b[k+1][t]+c[t]-c[j-1]);
  }
 }
    cout<<b[1][n];
    return 0;
}

コード3

#include
#include
using namespace std;
int n,a[101],b[101][101],s[101];//b[i][j]    i  ，   j         
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
    for(int l=1;l<=n;l++)//    
 {
  for(int i=1;i<=n;i++)//    
  {
   b[i][l]=0x7f7f7f7f;
   for(int j=1;j<l;j++)b[i][l]=min(b[i][l],b[i+j][l-j]+b[i][j]+s[l+i-1]-s[i-1]);
   if(l==1)b[i][l]=0;
  }
 }
    cout<<b[1][n];
    return 0;
}