[動態規劃]NOIP模擬題：整理書本 book

【問題描述】

Ztc想把他滿屋子的書整理一下。爲了應付繁重的學習任務，ztc已經筋疲力盡了，於是他向你求助，請你幫他計算他最少需要花費多少力氣。

書本分成若干堆，呈直綫排布。每一堆的書本都有重量w和價值v。Ztc的任務是將所有書合成一堆。因爲Ztc很看重書本的價值，所以他認爲合併i，j兩堆的書所需要的力氣爲w[i]-v[i]+w[j]-v[j]。合併後的書堆的重量和價值均爲合併前兩堆書的重量和價值的總和。也就是說，合併i．j兩堆的書後，w=w[i]+w[j],v=v[i]+v[j]。小智個人不願意走來走去，所以合併只能在相鄰兩堆書本間進行。書本合併前後，位置不變。如將1，2，3中的1，2進行合併，那麼合併結果爲3，3，再將3，3合併爲6(1，2，3，6指重量)。

【輸入】

輸入文件book.in的第一行是一個整數n(2≤n≤400)。

第2～n+1行每行兩個整數w和v(0<v<w≤1000)。

【輸出】

輸出文件book.out共一行，這一行只有一個整數f，表示最小力氣。

【輸入輸出樣例】

book.in

3

6 5

9 7

11 2

book.out

15

【輸入輸出樣例解釋】

先將前兩堆合併，再將合併後的書堆與剩餘的一堆合併。

【限制】

30％的數據滿足：2≤n≤100

100％的數據滿足：2≤n≤400

【分析】

經典的石子歸併問題，動態規劃。

狀態設定：

       W[i]表示第i本書的重量
       V [i]表示第i本書的價值
       SumW[i,j]表示第i本書 到 第j本書 重量的總和
       SumV [i,j]表示第i本書 到 第j本書 價值的總和
       F[i,j]表示從第i本書 到 第j本書 合併的最小代價。
邊界條件： 
       F[i][i]=0  
狀態轉移方程：
      F[i,j]=min{F[i,k]+F[k+1][j]+SumW[i,j]-SumV[i,j]}(i<=k<=j-1)
目標結果：
      F[1][N]


【我的代碼】
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
#define M 401
#define INF 1000000000
int N;         
int f[M][M];   //f[i,j]表示從第i個到第j個歸併的最小代價
int sum1[M][M]; //sum[i,j]表示第i個數到第j個數W的總和
int sum2[M][M]; //sum[i,j]表示第i個數到第j個數V的總和
int stone1[M];  //書本的重量
int stone2[M];  //書本的重要度


int main()
{
    freopen("book.in","r",stdin);
    freopen("book.out","w",stdout);
    int i,j,k;
    cin>>N;
    for(i=1;i<=N;i++)
        scanf("%d %d\n",&stone1[i],&stone2[i]);

    for(i=1;i<=N;i++)
    {
        f[i][i]=0;
        sum1[i][i]=stone1[i];
        for(j=i+1;j<=N;j++)
            sum1[i][j]=sum1[i][j-1]+stone1[j];
    }

    for(i=1;i<=N;i++)
    {
        //f[i][i]=0;
        sum2[i][i]=stone2[i];
        for(j=i+1;j<=N;j++)
            sum2[i][j]=sum2[i][j-1]+stone2[j];
    }

   
    for(int len=2;len<=N;len++)
    {
        for(i=1;i<=N-len+1;i++)
        {
            j=i+len-1;
            f[i][j]=INF;  
            for(k=i;k<=j-1;k++)
            {
                if(f[i][j]>f[i][k]+f[k+1][j]+sum1[i][j]-sum2[i][j])
                    f[i][j]=f[i][k]+f[k+1][j]+sum1[i][j]-sum2[i][j];
            }
        }
    }
    printf("%d\n",f[1][N]);
    return 0;
}