[動态規劃] aoapc-ch9 硬币問題 （DAG的不固定起點終點的最長短路）

題目

思路

DAG的固定起點和終點的最短路和最航路問題。

0.抽象：初始狀态為S，末狀态為0，每次使用一個硬币，狀态由S’變為S’-V[i]。為DAG。

1.狀态及名額函數定義：mind[i]：0->i最短路長度，maxd[i]：0->i最長路長度。

2.狀态轉移方程：

mind(i)=min{mind(i−Vx)+1,x∈[0,n)} m i n d ( i ) = m i n { m i n d ( i − V x ) + 1 , x ∈ [ 0 , n ) }

maxd(i)=max{maxd(i−Vx)+1,x∈[0,n)} m a x d ( i ) = m a x { m a x d ( i − V x ) + 1 , x ∈ [ 0 , n ) }

3.代碼實作時，特殊值的使用：

d[i] = -1 : 尚未計算。

d[i] < 0 || d[i] > INF : 計算了，但無論如何都走不到終點。

d[i] = 0或其它 : 計算了，正常值。

4.代碼實作采用兩種方法：記憶化搜尋與遞推。

總體來說遞推稍快，因為記憶化搜尋需要調用系統棧，而遞推隻是單純循環。

- 對于記憶化搜尋的輸出方法，采用“類記憶化搜尋”。

- 對于遞推的輸出方案，采用“遞推順帶記錄輸出資料”。

代碼

1.記憶化搜尋，輸出ans

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define _for(i,a,b) for (int i =(a); i<(b); i++)
using namespace std;

const int maxn =  + ;
const int INF =  << ;
int n, S, V[maxn], d[maxn];

int dp1(int x) {
    int &ans = d[x];
    if (ans != -) return ans; //未被通路過
    ans = INF;  //意思是，無法達到
    _for(i, , n)
        if (x - V[i] >= )
            ans = min(ans, dp1(x - V[i]) + );
    return ans;
}

int dp2(int x) {
    int &ans = d[x];
    if (ans != -) return ans; //未被通路過
    ans = -INF;  //意思是，無法達到
    _for(i, , n)
        if (x - V[i] >= )
            ans = max(ans, dp2(x - V[i]) + );
    return ans;
}

int main() {
    scanf("%d%d", &n, &S);
    _for(i, , n) scanf("%d", &V[i]);

    memset(d, -, sizeof(d));
    d[] = ;
    int minans = dp1(S);
    if (minans >= INF) minans = -;

    memset(d, -, sizeof(d));
    d[] = ;
    int maxans = dp2(S);
    if (maxans < ) maxans = -;

    printf("%d %d\n", minans, maxans);

    return ;
}
           

2.遞推，輸出ans

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define _for(i,a,b) for (int i =(a); i<(b); i++)
#define _rep(i,a,b) for (int i =(a); i<=(b); i++)
using namespace std;

const int maxn =  + ;
const int INF =  << ;
int n, S, V[maxn], mind[maxn], maxd[maxn];


int main() {
    scanf("%d%d", &n, &S);
    _for(i, , n) scanf("%d", &V[i]);

    _rep(x, , S) {  // 遞推每個元素都會周遊到，是以不用-1做是否通路
        mind[x] = INF;
        maxd[x] = -INF;
    }
    mind[] = ;
    maxd[] = ;

    _rep(x, , S)  // 從已知邊界的一側開始遞推
        _for(i,,n)
            if (x >= V[i]) {
                mind[x] = min(mind[x], mind[x - V[i]] + );
                maxd[x] = max(maxd[x], maxd[x - V[i]] + );
            }

    if (mind[S] >= INF) mind[S] = -;
    if (maxd[S] < ) maxd[S] = -;
    printf("%d %d\n", mind[S], maxd[S]);

    return ;
}
           

3.記憶化搜尋，輸出方案

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define _for(i,a,b) for (int i =(a); i<(b); i++)
using namespace std;

const int maxn =  + ;
const int INF =  << ;
int n, S, V[maxn], d[maxn];

int dp1(int x) {
    int &ans = d[x];
    if (ans != -) return ans; //未被通路過
    ans = INF;  //意思是，無法達到
    _for(i, , n)
        if (x - V[i] >= )
            ans = min(ans, dp1(x - V[i]) + );
    return ans;
}

int dp2(int x) {
    int &ans = d[x];
    if (ans != -) return ans; //未被通路過
    ans = -INF;  //意思是，無法達到
    _for(i, , n)
        if (x - V[i] >= )
            ans = max(ans, dp2(x - V[i]) + );
    return ans;
}

void print_ans(int x) {
    _for(i,,n)
        if (x >= V[i] && d[x] == d[x - V[i]] + ) {
            printf("%d ", i + );   // 注意此處是列印邊，而不是列印頂點，與矩形嵌套那個題厘清
            print_ans(x - V[i]);
            break;
        }
}

int main() {
    scanf("%d%d", &n, &S);
    _for(i, , n) scanf("%d", &V[i]);

    memset(d, -, sizeof(d));
    d[] = ;
    int minans = dp1(S);
    if (minans >= INF) printf("impossible\n");
    else { print_ans(S); printf("\n"); }

    memset(d, -, sizeof(d));
    d[] = ;
    int maxans = dp2(S);
    if (maxans < ) printf("impossible\n");
    else { print_ans(S); printf("\n"); }

    return ;
}
           

4.遞推，輸出方案

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define _for(i,a,b) for (int i =(a); i<(b); i++)
#define _rep(i,a,b) for (int i =(a); i<=(b); i++)
using namespace std;

const int maxn =  + ;
const int INF =  << ;
int n, S, V[maxn], mind[maxn], maxd[maxn], min_coin[maxn], max_coin[maxn];

void print_ans(int *coin,int x) {
    while (x) {
        printf("%d ", coin[x]+);
        x -= V[coin[x]];
    }
}

int main() {
    scanf("%d%d", &n, &S);
    _for(i, , n) scanf("%d", &V[i]);

    _rep(x, , S) {  // 遞推每個元素都會周遊到，是以不用-1做是否通路
        mind[x] = INF;
        maxd[x] = -INF;
    }
    mind[] = ;
    maxd[] = ;

    _rep(x, , S)  // 從已知邊界的一側開始遞推
        _for(i, , n)
        if (x >= V[i]) {
            if (mind[x] > mind[x - V[i]] + ) {  // 此處不是>=是因為要按字典序輸出方案
                mind[x] = mind[x - V[i]] + ;
                min_coin[x] = i;
            }
            if (maxd[x] < maxd[x - V[i]] + ) {
                maxd[x] = maxd[x - V[i]] + ;
                max_coin[x] = i;
            }
        }

    if (mind[S] >= INF) printf("impossible\n");
    else { print_ans(min_coin, S); printf("\n"); }
    if (maxd[S] < ) printf("impossible\n");
    else { print_ans(max_coin, S); printf("\n"); }

    return ;
}