区間dp——合併金貨

リンク:https://www.nowcoder.com/questionTerminal/6d3ccbc5b6ad4f12b8fe4c97eaf969e0出典:牛客網
N山の金貨が一列に並んでいて、i山目にはC[i]塊の金貨が入っています.合併するたびに隣接する2つの金貨を1つの金貨に統合し、コストはこの2つの金貨の数の和になります.N-1回の合併を経て、最終的にすべての金貨を一山に合併した.金貨を一山にまとめる最低コストを見つけてください.
ここで、1<=N<=30、1<=C[i]<=100
説明を入力:
第1行は1つの数字Nを入力してN山の金貨があることを表します
2行目にN個の数字を入力して金貨の山ごとの数量C[i]を表す
出力の説明:

       S              

例1
入力

4
3 2 4 1

しゅつりょく

20

例2
入力

30
10 20 30 40 50 60 70 80 90 100 99 89 79 69 59 49 39 29 19 9 2 12 22 32 42 52 62 72 82 92

しゅつりょく

7307

隣接するものに出会ったら,区間dpに考えなければならない.
初期化に注意してください.
コード:

#include
using namespace std;
const int INF=0x3f3f3f3f;
int main()
{
    int n;
    int c[50],sum[50],dp[50][50];
    while(scanf("%d",&n)!=EOF){
    memset(dp,INF,sizeof(dp));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
        sum[i]=sum[i-1]+c[i];
        dp[i][i]=0;
    }
    for(int len=1;len<=n;len++){///    
        for(int i=1;i+len<=n;i++){/// 
            int wei=i+len;
            for(int k=i;k