POJ 1160 （區間DP+四邊形優化）

POJ 1160 （區間DP+四邊形優化）

這個轉移方程不好想，尤其是一段值的解是中間，不明覺厲。dp[i][j] 用i個郵局，覆蓋前j個村莊的最小值。

還有就是區間dp的平行四邊形優化，這個題的轉移方程並不是“區間DP”，所以枚舉狀態要逆著（很花時間），且用一個郵局覆蓋都是從0斷開了相當於沒有斷開。

類比於石子歸並，矩陣鏈乘等標准區間DP，其所需狀態之前就已經獲得，不用倒推

#include 
#include 
#include 
using namespace std;

const int NN=310;
const int INF=0x7fffffff;

int n,m;
int s[NN],dp[NN][NN],w[NN][NN],p[NN][NN];

void get_w()//求在i~j號村莊間建一個郵局的最小距離和
{
    for (int i=1; i

//直線取石子問題的平行四邊形優化：

#include 
#include 
#include 

using namespace std;
const int INF = 1 << 30;
const int N = 1005;

int dp[N][N];
int p[N][N];
int sum[N];
int n;

int getMinval()
{
    for(int i=1; i<=n; i++)
    {
        dp[i][i] = 0;
        p[i][i] = i;//這個自己跟自己乘自然是以自己為分割了。
    }
    for(int len=1; len