さいしょうこうかんけつごうもんだい

タイトルの説明
運動場にはn山の石が一直線に並んでいる.今、石を順番に積み上げます.毎回隣接する2つの石を選んで新しい山に統合するしかなく、新しい石の数をこの合併の得点として記録することを規定しています.1回目の合併前に隣接する2つの石の順序を調整することができる.上記の条件下でn堆石を一堆に統合した最小得点と初回交換の位置を計算した.
入力フォーマット
入力データは2行あり、そのうち、1行目は石積み数n≦100である.2行目は順番に並んだ各石積み数(≦20)で、2つの数の間をスペースで区切っています.
しゅつりょく
マージの最小スコアを出力します.
サンプル入力
3 2 5 1
サンプル出力
11
問題の構想を解く:本題は経典の合併類の問題で、区間DPに属して、合併類の問題は以前のNOIとNOIP(2006年のエネルギーのネックレス)甚だしきに至ってはIOI(1995合併の砂)ですべて試験して、十分にその総要性を説明します.マージクラスの問題には2つの解法があります.解法1:f[i][j]はiから(iを含む)後ろにj個を合併する最適解を表し、この解法はテーマがリングに設計されている場合に便利である(NOIP 2006エネルギーネックレス).解法2 f[i][j]はiからjに統合された最適解を表し,この解法は線形問題での使用に適している.次に変数kを用いてi j間をループして解くとよいが,両手法とも境界の処理に注意する必要があり,そうしないと意外なエラーが発生する可能性があることに注意する.具体的な転送方程式はコードで与えられる.(本題では、データが大きくないので列挙すればよいことに気づく必要があります).
解法1:

#include
#include
#include
#include
using namespace std;
const int N=105;
int a[N],f[N][N],sum[N][N];
int main()
{
    int n,ans=0x7fffffff;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    for (int ch=1;ch

解法2:

#include
#include
#include
using namespace std;
const int MAX=1010;
const int INF=1000000000;
int f[MAX][MAX];
int main()
{
    int n;
    int s[MAX];
    int a[MAX],ans(INF);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for (int ch=1;ch

コードの中にはいくつかの細部に気づいていないかもしれませんが、どうぞお許しください.コメントの中で指摘してください.ありがとうございます.