[动态规划] 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 ;
}