NYOJ737

題意：給n堆石子，按照順序排列，隻能相鄰兩堆石子合并，求最後合并為一堆時所花費的最小代價，石子合并代價為兩堆石子之和。

輸入：

n（石子堆數）

Xi（每堆石子個數）

輸出：

T（最小代價）

思路：經典石子歸并問題，區間DP，原諒我對DP并不怎麼感冒，簡單點來說，首先預處理記下i到j的石子總數，用數組存放，然後在DP的過程中，因為求解的是最小代價，我們可以這樣想，先找出兩堆石子所有情況中最小的，然後再這個基礎上依次轉移到三堆，四堆，直到n堆，是以複雜度n^3,在每堆情況裡面，狀态轉移方程為 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);這裡i-k是一堆，（k+1）-j是一堆，然後要加上這兩堆的花費之和，是以遞歸求解就可以得到1-n堆石子最小代價花費了。

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
#define M 101
#define MAX 10000000
int n,dp[M][M],sum[M][M],s[M];
int main()
{
    int i,j,k;
    memset(dp,0,sizeof(dp));
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&s[i]);
        sum[i][i]=s[i];
        for(j=i+1; j<=n; j++)
            sum[i][j]=sum[i][j-1]+s[j];
    }
    for(int k=2; k<=n; k++)
    {
        for(i=1; i<=n-k+1; i++)
        {
            j=i+k-1;
            dp[i][j]=MAX;
            for(k=i; k<=j-1; k++)
                dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[i][j]);
        }
    }
    printf("%d\n",dp[1][n]);
    return 0;
}