DAG上DP的示例分析

這篇文章給大家分享的是有關(guān)DAG上DP的示例分析的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。

DAG即有向無(wú)環(huán)圖

這里舉出兩經(jīng)典的DAG模型，嵌套矩形和硬幣問(wèn)題

嵌套矩形(不固定起點(diǎn)最長(zhǎng)路及其字典序)

描述

有n個(gè)矩形，每個(gè)矩形可以用 (a,b) 來(lái)描述，表示長(zhǎng)和寬
矩形 X(a,b) 可以嵌套在矩形 Y(c,d) 中，當(dāng)且僅當(dāng) a<c,b<d 或者 b<c,a<d(旋轉(zhuǎn)90度)
例如(1,5)可以嵌套在(6,2)內(nèi)，但不能嵌套在(3,4)中
你的任務(wù)是選出盡可能多的矩形排成一行，使得除最后一個(gè)外，每一個(gè)矩形都可以嵌套在下一個(gè)矩形內(nèi)

分析

矩形間的“可嵌套”關(guān)系是一個(gè)典型的二元關(guān)系，二元關(guān)系可以用圖來(lái)建模
如果矩形X可以嵌套在Y中，則就從X到Y(jié)連一條有向邊
這個(gè)圖是無(wú)環(huán)的，因?yàn)橐粋€(gè)矩形無(wú)法直接或或間接的嵌套在自己的內(nèi)部
也即是說(shuō)這是以一個(gè)DAG
因此，我們就是在求DAG上的不固定起點(diǎn)的最長(zhǎng)路徑

解題

設(shè) d(i) 表示從結(jié)點(diǎn) i 出發(fā)的最長(zhǎng)路長(zhǎng)度

第一步只能走到它的相鄰點(diǎn)，那么我們就有：

其中，E為邊集，則最終答案是所有的d(i)中的最大值，因此可以用遞推或者記憶化搜索計(jì)算

第一步，建圖，假如用鄰接矩陣將矩形間的關(guān)系保存在矩陣G中

第二步，編寫記憶化搜索程序(調(diào)用前先初始化數(shù)組為0)

第三步，按字典序輸出最佳的方案

假如有這樣的 5 個(gè)矩形，輸入的邊長(zhǎng)分別是：

建圖

先對(duì)長(zhǎng)和寬來(lái)此排序，再按照要求構(gòu)圖， 完成之后，直接記憶化搜索，但由于是不固定起點(diǎn)的，所以不能只從第一個(gè)點(diǎn)搜索，而是每個(gè)點(diǎn)都要開(kāi)始搜索

搜索代碼：

int dp(int i)
{
    int& ans = d[i];//為表項(xiàng)d[i]聲明一個(gè)引用ans 
    if(ans > 0)  
        return ans;
    ans = 1;
    for(int j=1;j<n;j++)
        if(G[i][j])
			ans = max(ans,dp(j)+1);
    return ans;
}

這里使用了一個(gè)技巧：為表項(xiàng)d[i]聲明一個(gè)引用ans，這樣，任何對(duì)ans的讀寫實(shí)際上都是在對(duì)d[i]進(jìn)行。當(dāng)d[i]換成d [i] [j] [k] [l] [m] [n] 這樣很長(zhǎng)的名字時(shí)，該技巧的優(yōu)勢(shì)就會(huì)很明顯

然后我們要考慮如何輸出字典序最小的方案
字典序只是消除并列名次的方法，我們最根本的任務(wù)還是求出最長(zhǎng)路
在把所有的d值計(jì)算出來(lái)后，選擇最大的d[i]所對(duì)應(yīng)的i，而如果有多個(gè)i，則選擇最小的i，來(lái)保證字典序最小
接下來(lái)選擇 d(i) = d(j) +1 且i, j ∈E 的任何一個(gè)j，但是為滿足字典序最小，需選擇最小的j，代碼如下

void print_ans(int i){
    printf("%d ", i);//第一次i代表最長(zhǎng)路的起點(diǎn)節(jié)點(diǎn)，以后均代表從該節(jié)點(diǎn)開(kāi)始的路徑
    for(int j = 1; j <= n; j++)
        if(G[i][j] && d[i] == d[j]+1)// 如果該圖滿足可嵌套，且d[i] = d[j] +1
        {
            print_ans(j);
            //立即輸出從節(jié)點(diǎn)j開(kāi)始的路徑
            break;
        }
}

完整題解代碼

#include<stdio.h>
#include<string.h>
#define MAXN 100+1
int n, G[MAXN][MAXN];//存圖
int x[MAXN], y[MAXN], d[MAXN]; 

int dp(int i){
    int& ans = d[i];//為表項(xiàng)d[i]聲明一個(gè)引用ans 
    if(ans > 0)  
        return ans;
    ans = 1;
    for(int j=1;j<=n;j++)
        if(G[i][j])
			ans = max(ans,dp(j)+1);
    return ans;
}

void print_ans(int i){
    printf("%d ", i);//第一次i代表最長(zhǎng)路的起點(diǎn)節(jié)點(diǎn)，以后均代表從該節(jié)點(diǎn)開(kāi)始的路徑
    for(int j = 1; j <= n; j++)
        if(G[i][j] && d[i] == d[j]+1)// 如果該圖滿足可嵌套，且d[i] = d[j] +1
        {
            print_ans(j);
            //立即輸出從節(jié)點(diǎn)j開(kāi)始的路徑
            break;
        }
}

int main()
{
    int t, ans, best;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%d%d", &x[i], &y[i]);
        if(x[i] > y[i]){
            t = x[i];
            x[i] = y[i];
            y[i] = t;   
            //保證X[]存的是長(zhǎng)，Y[]存的是寬
        }
    }
    memset(G, 0, sizeof(G));
    for(int i = 1; i <= n; i++)//建圖
        for(int j = 1; j <= n; j++)
            if(x[i] < x[j] && y[i] < y[j])
                G[i][j] = 1;//如果第i個(gè)矩形的長(zhǎng)寬均小于第j個(gè)，使圖相應(yīng)的值為1

    ans = 0;
    for(int i = 1; i <= n; i++)//依次遞推所有的的節(jié)點(diǎn)
        if(dp(i) > ans){
            best = i;//best是最小字典序
            ans = dp(i);
        }
    printf("ans=%d\n", ans);//表示最長(zhǎng)路長(zhǎng)度
    print_ans(best);
    printf("\n");
    return 0 ;
}

硬幣問(wèn)題(固定終點(diǎn)的最長(zhǎng)路和最短路)

描述

有 n 種硬幣，面值分別為V1, V2······Vn，每種都有無(wú)限多
給定非負(fù)整數(shù) S ，可以選用多少個(gè)硬幣，使得面值之和恰好為S？
輸出硬幣數(shù)目的最小值和最大值

分析

看上去和嵌套矩形問(wèn)題很不一樣，但本題的本質(zhì)也是DAG上的路徑問(wèn)題
將每種面值看作一個(gè)節(jié)點(diǎn)，設(shè)初始狀態(tài)為S，目標(biāo)狀態(tài)為0
若當(dāng)前在狀態(tài) i，每使用一個(gè)硬幣 j，狀態(tài)便轉(zhuǎn)移到i - Vj

解題

最長(zhǎng)路和最短路的求法是類似的，由于終點(diǎn)固定，d(i) 的確切含義變?yōu)閺慕Y(jié)點(diǎn)i出發(fā)到結(jié)點(diǎn)0的最長(zhǎng)路徑長(zhǎng)度

int dp(int S)
{
    int& ans = d[S];
    if(ans >= 0) 
        return ans;
    ans = 0;
    for(int i=1;i<=n;i++)
        if(S >= V[i])    
            ans = max(ans,dp(S-V[i])+1);
    return ans;
}

回顧一下嵌套矩形的找最長(zhǎng)路

int dp(int i)
{
    int& ans = d[i];//為表項(xiàng)d[i]聲明一個(gè)引用ans 
    if(ans > 0)
        return ans;
    ans = 1;
    for(int j=1;j<n;j++)
        if(G[i][j])
			ans = max(ans,dp(j)+1);
    return ans;
}

由于在本題中，路徑長(zhǎng)度是可以為0的(S本身可以是0)，所以不能再用d=0表示這個(gè)d值還沒(méi)有算過(guò)，初始化時(shí)也不能再把d全設(shè)為0，而要設(shè)置為一個(gè)負(fù)值令初始狀態(tài)不合法，這里可以用 -1 來(lái)表示沒(méi)有算過(guò)，初始化時(shí)只需用memset(d,-1,sizeof(d))即可，同時(shí) if(ans>0) 也要改成 if(ans>=0)

但其實(shí)，由于結(jié)點(diǎn)S不一定真的能到達(dá)結(jié)點(diǎn)0，所以需要用特殊的d[S]值表示“無(wú)法到達(dá)”，但在上述代碼中，如果S根本無(wú)法繼續(xù)往前走，返回值是0，將被誤以為是“已到達(dá)終點(diǎn)”的意思

如果把a(bǔ)ns初始化為-1呢？但-1代表“還沒(méi)算過(guò)”，所以返回-1相當(dāng)于放棄了自己的勞動(dòng)成果

如果把a(bǔ)ns初始化為一個(gè)很大的整數(shù)，從目前來(lái)看，它也會(huì)被認(rèn)為是“還沒(méi)算過(guò)”，但至少可以和所有d的初值分開(kāi)——只需把代碼中if(ans>=0)改為if(ans!=-1)即可

int dp(int S)
{
    int& ans = d[S];
    if(ans != -1)   
        return ans;
    ans = -(1<<30);
    for(int i=1;i<=n;i++){
        if(S >= V[i])    
            ans = max(ans,dp(S-V[i])+1);
    }
    return ans;
}

另一個(gè)常用的解決方法是不用特殊值表示“還沒(méi)算過(guò)”，而用另外一個(gè)數(shù)組 vis[i] 表示狀態(tài) i 是否被訪問(wèn)過(guò)

int dp(int S)
{
    if(vis[S])  
        return d[S];
    vis[S] = -1;
    int& ans = d[S];
    ans = -(1<<30);
    for(int i=1;i<=n;i++)
        if(S >= V[i])    
            ans = max(ans,dp(S-V[i])+1);
    return ans;
}

本題要求最小、最大兩個(gè)值，記憶化搜索就必須寫兩個(gè)，在這種情況下，用遞推更加方便(此時(shí)需注意遞推的順序)

minv[0] = maxv[0] = 0;
for(int i=1;i<=S;i++){
    minv[i] = INF;//minv[i]表示最小值
    maxv[i] = -INF;//maxv[i]表示最大值
}
for(int i=1;i<=S;i++){
    for(int j=1;j<=n;j++){
        if(i >= V[j]){
            minv[i] = min(minv[i],minv[i-V[j]]+1);
            maxv[i] = max(maxv[i],maxv[i-V[j]]+1);
        }
    }
}
printf("%d %d\n",minv[S],maxv[S]);

如何輸出字典序最小的方案呢？剛剛介紹的方法仍然適用，如下所示：

void print_ans(int* d,int S)
{
    for(int i=1; i<=n; i++)
    {
        if(S>=V[i] && d[S]==d[S-V[i]]+1)
        {
            printf("%d ",i);
            print_ans(d,S-V[i]);
            break;

        }
    }
}

上題打印的是路徑上的點(diǎn)，而這里打印的是路徑上的邊

另外一種常用的打印路徑的方法：遞推時(shí)直接用min_coin[S]記錄滿足min[S]==min[S-V[i]]+1的最小的i，則打印路徑時(shí)可以省去print_ans()中的循環(huán)，并可以方便地把遞歸改成迭代 (當(dāng)然，原來(lái)的也可以改成迭代，但不那么自然）具體代碼如下

for(int i=1;i<=S;i++){
    for(int j=1;j<=n;j++){
        if(i >= V[j]){
            if(min[i]>min[i-V[j]]+1){
                min[i] = min[i-V[j]]+1;
                min_coin[i] = j;
            }
            if(max[i]<max[i-V[j]]+1){
                max[i] = max[i-V[j]]+1;
                max_coin[i] = j;
            }
        }
    }
}

小結(jié)

由于DAG最長(zhǎng) (短）路的特殊性，有兩種“對(duì)稱”的狀態(tài)定義方式。

狀態(tài)1：設(shè) d(i) 為從 i 出發(fā)的最長(zhǎng)路，則

狀態(tài)2：設(shè) d(i) 為以 i 結(jié)束的最長(zhǎng)路，則

如果使用狀態(tài)2，“硬幣問(wèn)題”就變得和“嵌套矩形問(wèn)題”幾乎一樣了 (唯一的區(qū)別是“嵌套矩形問(wèn)題”還需要取所有d (i）的最大值）！我們?cè)谏厦娼榻B了比較麻煩的狀態(tài)1，主要是為了展示一些常見(jiàn)技巧和陷阱，實(shí)際比賽中不推薦使用。

使用狀態(tài)2時(shí)，有時(shí)還會(huì)遇到一個(gè)問(wèn)題：狀態(tài)轉(zhuǎn)移方程可能不好計(jì)算，因?yàn)樵诤芏鄷r(shí)候，可以方便地枚舉從某個(gè)結(jié)點(diǎn)i出發(fā)的所有邊 (i , j），卻不方便“反著”枚舉 (j , i）。特別是在有些題目中，這些邊具有明顯的實(shí)際背景，對(duì)應(yīng)的過(guò)程不可逆。這時(shí)需要用“刷表法”

什么是“刷表法”呢？傳統(tǒng)的遞推法可以表示成“對(duì)于每個(gè)狀態(tài) i，計(jì)算f (i）”，或者稱為“填表法”。這需要對(duì)于每個(gè)狀態(tài) i，找到f (i）依賴的所有狀態(tài)，在某些情況下并不方便。另一種方法是“對(duì)于每個(gè)狀態(tài)i，更新f (i）所影響到的狀態(tài)”，或者稱為“刷表法”。對(duì)應(yīng)到DAG最長(zhǎng)路的問(wèn)題中，就相當(dāng)于按照拓?fù)湫蛎杜e i，對(duì)于每個(gè) i，枚舉邊 (i , j），然后更新d[j] = max(d[j],d[i]+1)。注意，一般不把這個(gè)式子叫做“狀態(tài)轉(zhuǎn)移方程”，因?yàn)樗皇且粋€(gè)可以直接計(jì)算d[j]的方程，而只是一個(gè)更新公式

提示：傳統(tǒng)的遞推法可以表示成“對(duì)于每個(gè)狀態(tài) i，計(jì)算f (i）”，或者稱為“填表法”。這需要對(duì)于每個(gè)狀態(tài) i，找到f (i）依賴的所有狀態(tài)，在某些時(shí)候并不方便。另一種方法是“對(duì)于每個(gè)狀態(tài) i，更新f (i）所影響到的狀態(tài)”，或者稱為“刷表法”，有時(shí)比填表法方便。但需要注意的是，只有當(dāng)每個(gè)狀態(tài)所依賴的狀態(tài)對(duì)它的影響相互獨(dú)立時(shí)才能用刷表法

例題

A - A Spy in the Metro

某城市的地鐵是線性的，有n（2≤n≤50）個(gè)車站，從左到右編號(hào)為1～n

有M1輛列車從第1站開(kāi)始往右開(kāi)，還有M2輛列車從第n站開(kāi)始往左開(kāi)

在時(shí)刻0，Mario從第1站出發(fā)，目的是在時(shí)刻T（0≤T≤200）會(huì)見(jiàn)車站n的一個(gè)間諜，在車站等車時(shí)容易被抓，所以她決定盡量躲在開(kāi)動(dòng)的火車上，讓在車站等待的總時(shí)間盡量短，列車靠站停車時(shí)間忽略不計(jì)，且Mario身手敏捷，即使兩輛方向不同的列車在同一時(shí)間靠站，Mario也能完成換乘。

輸入：

第1行為n，
第2行為T，
第3行有n－1個(gè)整數(shù)t1,t2,…,tn?1（1≤ti≤70），
其中ti表示地鐵從車站i到i＋1的行駛時(shí)間（兩個(gè)方向一樣）
第4行為M1（1≤M1≤50），即從第1站出發(fā)向右開(kāi)的列車數(shù)目
第5行包含M1個(gè)整數(shù)d1, d2,…, dM1（0≤di≤250，di＜di+1），即各列車的出發(fā)時(shí)間。
第6、7行描述從第n站出發(fā)向左開(kāi)的列車，格式同第4、5行

輸出僅包含一行，即最少等待時(shí)間。無(wú)解輸出impossible

分析

時(shí)間是單向流逝的，是一個(gè)天然的“序”，而影響到?jīng)Q策的只有當(dāng)前時(shí)間和所處的車站
可以用 d(i,j) 表示：在時(shí)刻i，處于在車站j（編號(hào)為1～n）時(shí)，最少還需要等待的時(shí)間
邊界條件是d(T,n)=0，其他 d(T,i)（i不等于n）為正無(wú)窮

有如下3種決策。

• 等1分鐘。

• 搭乘往右開(kāi)的車（如果有）

• 搭乘往左開(kāi)的車（如果有）

在程序中定義一個(gè)三維數(shù)組has_train
has_train [t] [i] [0] 表示：時(shí)刻t，在車站i是否有往右開(kāi)的火車
has_train [t] [i] [1] 表示：時(shí)刻t，在車站i是否有往左開(kāi)的火車

核心代碼如下：

for (int i = 1; i <= n-1; i++)
    dp[T][i] = INF;
dp[T][n] = 0;

for (int i = T-1; i >= 0; i++)
{
    for (int j = 1; j <=n ; j++)
    {
        dp[i][j] = dp[i+1][j] + 1;
        if(j<n && has_train[i][j][0] && i+t[j] <= T)
            dp[i][j] = min(dp[i][j],dp[i+t[j][j+1]])//右
        if(j>1 && has_train[i][j][1] && i+t[j-1] <= T)
            dp[i][j] = min(dp[i][j],dp[i+t[j-1][j-1]])//左
    }
}

if(dp[0][1])
    puts("impossible");
else
    cout<<dp[0][1]<<endl;

完整ac碼

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int INF=0x3f3f3f3f;
int t[50+10]；
int dp[200+10][50+10]；
int has_train[200+10][50+10][2];

int main()
{
    int n,T,M1,M2,flag;
    int casen=0;
    while(scanf("%d",&n)!=EOF&&n)
    {
        memset(has_train,0,sizeof(has_train));
        memset(t,0,sizeof(t));
        memset(dp,INF,sizeof(dp));
        scanf("%d",&T);
        for(int i=1; i<n; i++)
            scanf("%d",&t[i]);
        scanf("%d",&M1);
        for(int i=1; i<=M1; i++)
        {
            scanf("%d",&flag);
            for(int j=1; j<=n; j++)
            {
                flag+=t[j-1];
                has_train[flag][j][0]=1;
            }
        }
        scanf("%d",&M2);
        for(int i=1; i<=M2; i++)
        {
            scanf("%d",&flag);
            for(int j=n; j>=1; j--)
            {
                flag+=t[j];
                has_train[flag][j][1]=1;
            }
        }
        for(int i=1; i<=n-1; i++)
            dp[T][i]=INF;
        dp[T][n]=0;
        for(int i=T-1; i>=0; i--)
            for(int j=1; j<=n; j++)
            {
                dp[i][j]=dp[i+1][j]+1;
                if(j<n&&has_train[i][j][0]&&i+t[j]<=T)
                    dp[i][j]=min(dp[i][j],dp[i+t[j]][j+1]);
                if(j>1&&has_train[i][j][1]&&i+t[j-1]<=T)
                    dp[i][j]=min(dp[i][j],dp[i+t[j-1]][j-1]);
            }
        cout<<"Case Number "<<++casen<<": ";
        if(dp[0][1]>=INF)
            puts("impossible");
        else
            cout<<dp[0][1]<<endl;
    }
    return 0;
}

B - The Tower of Babylon

有n（n<=30)種立方體，每種都有無(wú)窮多個(gè)
要求選一些立方體，摞成一根盡量高的柱子(可以自行選擇哪一條作為高)
每個(gè)立方體的底面長(zhǎng)寬分別嚴(yán)格小于它下方立方體的底面長(zhǎng)寬

分析

任何時(shí)候都只有頂面（底=頂）尺寸會(huì)影響到后續(xù)決策，美增加一個(gè)立方體以后頂面長(zhǎng)和寬都必須嚴(yán)格減小，所以這個(gè)圖也是DAG，可以套用最長(zhǎng)路

由于只有三種面，每種立方體只要三個(gè)就夠了，每輸入一個(gè)立方體，就可以算作輸入了三個(gè)不同的立方體(任選一條邊作為高)，然后每一個(gè)立方體建邊，套用DAG上的dp模板

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100+10;

int n;
int H[MAXN];//記錄立方體i的高
int d[MAXN];//記錄以i為起點(diǎn)的最大高度
int G[MAXN][MAXN];//記錄i是否可以作為j的底，存圖
int a[3];//3種邊長(zhǎng)

struct Cube
{
    int x,y;//長(zhǎng)和寬
} cube[MAXN];

void have_edge(int i,int j)//i是否可以作為j的底，可以則連邊
{ 
    if(cube[i].x>cube[j].x && cube[i].y>cube[j].y)
        G[i][j]=1;
}

int dp(int i)
{
    int &ans = d[i];
    if(ans > 0)
        return ans;
    ans = H[i];
    for(int j=0; j<3*n; j++)
        if(G[i][j])
            ans=max(ans,H[i]+dp(j));
    return ans;
}

int main()
{
    int casen = 0;
    while(scanf("%d",&n)!=EOF&&n)
    {
        int ans=0;
        memset(d,0,sizeof(d));
        memset(G,0,sizeof(G));
        for(int i=0; i<n; i++)
        {
            scanf("%d %d %d",&a[0],&a[1],&a[2]);
            sort(a,a+3);
            cube[3*i].x=a[0],cube[3*i].y=a[1],H[3*i]=a[2];
            cube[3*i+1].x=a[0],cube[3*i+1].y=a[2],H[3*i+1]=a[1];
            cube[3*i+2].x=a[1],cube[3*i+2].y=a[2],H[3*i+2]=a[0];
        }
        for(int i=0; i<3*n; i++)
            for(int j=0; j<3*n; j++)
                have_edge(i,j);
        for(int i=0; i<3*n; i++)
            dp(i);
        for(int i=0 ; i<3*n ; i++)
            ans=max(ans,d[i]);
        printf("Case %d: maximum height = %d\n",++casen ,ans);
    }
    return 0;
}

C - Tour

給定平面n個(gè)點(diǎn)(n≤1000)的坐標(biāo)，按照x遞增的順序給出，保證各點(diǎn)的x都不同且都為正整數(shù)

你的任務(wù)是設(shè)計(jì)一條路線，從最左邊的點(diǎn)出發(fā)，嚴(yán)格向右走到達(dá)最右點(diǎn)再嚴(yán)格向左回到最左點(diǎn)，要求除了最左和最右，每個(gè)點(diǎn)恰好經(jīng)過(guò)一次，輸出最短路徑長(zhǎng)度

分析

從左到右再回來(lái)可以轉(zhuǎn)化成：兩個(gè)人同事從最左出發(fā)，沿著兩條不同的路徑走，最后到達(dá)最右點(diǎn)，并且除了起點(diǎn)和終點(diǎn)都只能有一個(gè)人經(jīng)過(guò)，自然想到可以用d(i,j)表示：一個(gè)人走到i點(diǎn)，另一個(gè)人走到j(luò)，還需要走多長(zhǎng)距離到達(dá)最右點(diǎn)
但是我們發(fā)現(xiàn)這樣狀態(tài)好像很難轉(zhuǎn)移，比如計(jì)算d(i,j)時(shí)，我們不知道能不能讓i上的1號(hào)同學(xué)走到i+1，因?yàn)閺臓顟B(tài)里看不出來(lái)i+1有沒(méi)有被j上的2號(hào)同學(xué)走過(guò)，也就是說(shuō)這個(gè)狀態(tài)定義的難以轉(zhuǎn)移

然后我們可以簡(jiǎn)單修改一下定義，讓d(i,j)表示：1~max[d(i,j)]全部走過(guò)，且兩個(gè)人目前位置是i和j時(shí)，還需要走多長(zhǎng)距離到達(dá)最右點(diǎn)，在這個(gè)定義下d(i,j)=d(j,i)，我們?cè)僖?guī)定始終有i>j，如果j>i了，只需要交換A、B的角色即可，即將i換為j，j換為i，這樣，不管是哪個(gè)人，下一步只能走到i＋1 , i＋2,…這些點(diǎn)

那么問(wèn)題又來(lái)了，如果走到i＋2，情況變成了“走過(guò)1~ i 和 i＋2，但是i＋1沒(méi)走過(guò)”，不合法

那么直接ban了這個(gè)路不就可以了，也就是說(shuō)，d(i,j)只允許其中一個(gè)人走到i＋1，而不能走到i＋2, i＋3,…
換句話說(shuō)，狀態(tài)d(i,j)只能轉(zhuǎn)移到d(i＋1,j)和d(i＋1,i)，這里意思就是：如果第一個(gè)人直接走到了i＋2，那么它再也無(wú)法走到i＋1了，只能靠第二個(gè)人走到i＋1，既然如此，現(xiàn)在就讓第二個(gè)人走到i＋1

邊界是d(n－1,j) = dist(n－1,n)＋dist(j,n)，其中dist(a,b)表示點(diǎn)a和b之間的距離，因?yàn)楦鶕?jù)定義，所有點(diǎn)都走過(guò)了，兩個(gè)人只需直接走到終點(diǎn)。所求結(jié)果是dist(1,2)＋d(2,1)，因?yàn)榈谝徊揭欢ㄊ悄硞€(gè)人走到了第二個(gè)點(diǎn)，根據(jù)定義，這就是d(2,1)

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1000+10;
double d[MAXN][MAXN];//第一個(gè)走到i第二個(gè)人走到j(luò)時(shí),還需要走多長(zhǎng)距離走完
int n;

struct point
{
    int x, y;//坐標(biāo)
}p[MAXN];

double dist(int A,int B)//p[A]到p[B]距離，隨便怎么實(shí)現(xiàn)，這里用hypot()
{
    int X = p[A].x - p[B].x;
    int Y = p[A].y - p[B].y;
    return hypot(X, Y);
}

double dp(int i, int j)//i>j
{
    double& ans = d[i][j];
    if (ans > 0)
        return ans;
    if (i == n - 1)
        return ans = dist(i, n) + dist(j, n);
    ans = min(dp(i + 1, j) + dist(i + 1, i), dp(i + 1, i) + dist(i + 1, j));
    return ans;
}

int main()
{
    while (cin >> n)
    {
        memset(d, 0, sizeof(d));
        for (int i = 1; i <= n; i++)
            cin >> p[i].x >> p[i].y;
        dp(2, 1);
        printf("%.2f\n", dist(2, 1) + d[2][1]);
    }
    return 0;
}

感謝各位的閱讀！關(guān)于“DAG上DP的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！