[Acwing] 282. 石子合并 區間DP

前言

傳送門 : https://www.acwing.com/problem/content/description/284/

感覺 和 線性dp差不多 隻是考慮狀态轉移的 時候不一樣了

(怎麼不一樣說不上來)

思路

要求 : 所有合并方案中 使得 答案最小的方案

狀态表示 : f[i][j] 表示從第 i 堆 合并到 第 j 堆的 最小方案

(為什麼呢？ 考感覺吧 QAQ)

狀态轉移 :

第 i 堆 合并到 第 j 堆 一定可以表示為

第 i 堆 先合并到 第 k堆 然後 第k+1堆 合并到 第 j堆

即 :

f [ i ] [ j ] = f [ i ] [ k ] + f [ k + 1 ] [ j ] f[i][j]= f[i][k]+f[k+1][j] f[i][j]=f[i][k]+f[k+1][j]

因為每次合并 都有 值的相加 但是又不能改變原來的

是以我們還需要多處理一個 字首和 數組

f [ i ] [ j ] = min ⁡ i ≤ k ≤ j − 1 f [ i ] [ k ] + f [ k + 1 ] [ j ] + s [ j ] − s [ i − 1 ] f[i][j]=\min _{i \leq k \leq j-1} f[i][k]+f[k+1][j]+s[j] - s[i-1] f[i][j]=mini≤k≤j−1​f[i][k]+f[k+1][j]+s[j]−s[i−1]

是以本題就好做了

(哈哈哈哈哈 好難啊)

CODE

/**
所有合并方式的 最小方案

方案是 (n-1)!

f[i][j]表示 将i到j合并成一堆的方案的集合 

狀态計算
i<j 時
f[i][j] = min(f[i][k]+f[k+1][j]+s[j]-s[i-1])

i = j 
f[i][j] = 0

**/
#include <bits/stdc++.h>
using namespace std;
const int N  = 310;
int a[N],s[N],f[N][N];

void solve()
{
    int n;
    cin>>n;

    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        s[i] +=s[i-1]+a[i];
    }


    for (int len = 1; len < n; len ++)   // len表示i和j堆下标的內插補點
    {
        for (int i = 1; i + len <= n; i ++)
        {
            int j = i + len; // 自動得到右端點
            f[i][j] = 1e8;
            for (int k = i; k <= j - 1; k ++)   // 必須滿足k + 1 <= j
            {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }

    cout<<f[1][n]<<endl;
}

int main()
{
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

/**
目前第i次操作  合并j和j-1堆 最小的花費
f[i][j][j-1]

f[0][1~n][1~n] 0

f[1][]
失敗的想法
**/

/**
   cin>>n;
    for(int i =1;i<=n;i++)
        cin>>a[i];

    for(int i =1;i<=n;i++)
    {
        for(int j=2;j<=n;j++)
        {
            f[i][j][j-1]
        }
    }
    for(int i=2;i<=n-1;i++)
    {

    }
失敗的嘗試  無法确定 i-1 和  i+1
**/