ACWING 282-石子合并(區間DP)

位址：​​https://www.acwing.com/problem/content/284/​​

題意：給一堆石子，相鄰的合并，問最後得到的最小花費，花費具體算法在題裡。

　　　  解析：

　　　　　　  對于此題，根據常識，對于最終狀态，是由兩團合并的。是以定義dp[i][j]表示區間i-j合并的最小值。

　　　　　　  二堆合并：dp[1][2]=dp[1][1]+dp[2][2]+sum[1~2];

　　　　　　　　　       即dp[i][i+1]=dp[i][i]+dp[i+1][i+1]+sum[i~i+1];

　　　　        三堆合并：dp[1][3]=min(dp[1][1]+dp[2][3],dp[1][2]+dp[3][3])+sum[1~3];

　　　　　　　　　     dp[i][i+2]=min(dp[i][i]+dp[i+1][i+2],dp[i][i+1]+dp[i+2][i+2])+sum[i~i+2];

　　　　       綜上推廣到第i堆到第j堆的合并，dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);

　　　　       三個for,相當于周遊每一個長度的區間。

　　　　       感覺有點floyed 的意思.....找中轉點

#include<iostream>
#include<cstdio>
#include<cstring>
const int maxn = 500;
const int inf = 1e9;
int dp[maxn][maxn];
int a[maxn],sum[maxn];
using namespace std;
int main()
{
    int n;
    cin>>n;
    sum[0]=0;
    for(int i = 1;i <= n ; i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    for(int len =2 ; len <= n ;len++)
    {
        for(int l = 1; l+len-1<=n; l++)
        {
            int r=l+len-1;
            dp[l][r]=inf;
            for(int k = l ; k  < r ; k ++)
            {
                dp[l][r]=min(dp[l][r],dp[l][k]+dp[k+1][r]+sum[r]-sum[l-1]);
            }
        }
    }
    cout<<dp[1][n]<<endl;
}