[動態規劃]OI練習題 ：刪數 remove 解題報告

               刪數  remove.cpp

【問題描述】

有 N 個不同的正整數數 x 1 , x 2 , ... x N 排成一排，我們可以從左邊或右邊去掉連續的 i 個數（只能從兩邊刪除數）， 1<=i<=n ，剩下 N-i 個數，再把剩下的數按以上操作處理，直到所有的數都被刪除爲止。

每次操作都有一個操作價值，比如現在要刪除從 i 位置到 k 位置上的所有的數。操作價值爲 |x i – x k |*(k-i+1) ，如果只去掉一個數，操作價值爲這個數的值。

任務

如何操作可以得到最大值，求操作的最大價值。

Input Data

輸入文件 remove.in 的第一行爲一個正整數 N ，第二行有 N 個用空格隔開的 N 個不同的正整數。

Output Data

輸出文件 remove.out 包含一個正整數，爲操作的最大值

約束和提示

3<=N<=100

N 個操作數爲 1..1000 之間的整數。

樣例

remove.in

6

54 29 196 21 133 118

remove.out

768

說明：經過 3 次操作可以得到最大值，第一次去掉前面 3 個數 54 、 29 、 196 ，操作價值爲 426 。第二次操作是在剩下的三個數（ 21 133 118 ）中去掉最後一個數 118 ，操作價值爲 118 。第三次操作去掉剩下的 2 個數 21 和 133 ，操作價值爲 224 。操作總價值爲 426+118+224=768 。

【分析】

動態規劃，是NOIP2007矩陣取數遊戲的升級版。

狀態設定：

     F[i,j] : 取前i個數、後j個數的最大操作總價值

可以定義一個GetValue函數，返回從第i個數到第j個數的操作值。

邊界條件：

    F[i,0]=GetValue(1,i);

    F[0,i]=GetValue(N-i+1,N)。

狀態轉移方程：

    F[i,j]=Max{ F[k,j]+GetValue(k+1,i) }  (0<=k<=i)

    F[i,j]=Max{ F[i,k]+GetValue(N-j+1,N-k) } (0<=k<=j)

目標結果：

    Max{ F[i][N-i] }  ( 0<=i<=N )

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int N;
int Num[101];
long long F[101][101];

void init()
{
    scanf("%d\n",&N);
    for (int i=1;i<=N;i++)
        cin>>Num[i];
}

int GV(int k,int i)
{
   
    if(k==0 && i==0)
        return 0;
   
    if(k==N+1 && i==N+1)
        return 0;
   
    if(k==0)
        k++;
    if(i==N+1)
        i--;
   
    if(k==i)
        return Num[i];
    int tmp=Num[k]-Num[i];
    if(tmp<0)
        tmp=-tmp;
    return tmp*(i-k+1);
}

void dp()
{
    for (int i=1;i<=N;i++)
        F[i][0]=GV(1,i);
   
    for (int i=1;i<=N;i++)
        F[0][i]=GV(N-i+1,N);
   
    int p;
    for (int i=1;i<=N;i++)
    {
        for (int j=1;j<=N;j++)
        {
            p=i+j;
            if(p>N)
                continue;
           
            long long m=0;
            for (int k=0;k<=i;k++)
            {
                int tmp=GV(k+1,i);
                if(m<F[k][j]+ tmp )
                    m=F[k][j]+ tmp;
            }
           
            F[i][j]=m;
           
            for (int k=0;k<=j;k++)
            {
                int tmp=GV(N-j+1,N-k);
                if(m<F[i][k]+tmp)
                    m=F[i][k]+tmp;
            }
           
            if(m>F[i][j])
                F[i][j]=m;
        }
    }
   
    long long M=0;
    for (int i=0;i<=N;i++)
    {
        if(M<F[i][N-i])
            M=F[i][N-i];
    }
    cout<<M<<endl;
}

int main()
{
    freopen("remove.in","r",stdin);
    freopen("remove.out","w",stdout);
    init();
   
    dp();
    return 0;
}