DAG上的动态规划

---

每天坚持做算法题，熟悉基本的套路，巩固语言基础，总结经验记下所学所想。

矩形问题

嵌套矩形问题。有n个矩形，每个矩形可以用两个整数a、b描述，表示它的长和宽。矩
形X(a,b)可以嵌套在矩形Y(c, d)中，当且仅当a＜c，b＜d，或者b＜c，a＜d（相当于把矩
形X旋转90°）。例如，(1, 5)可以嵌套在(6, 2)内，但不能嵌套在(3, 4)内。你的任务是选出尽
量多的矩形排成一行，使得除了最后一个之外，每一个矩形都可以嵌套在下一个矩形内。如
果有多解，矩形编号的字典序应尽量小。

HINT

矩形之间的“可嵌套”关系是一个典型的二元关系，二元关系可以用图来建模。如果矩
形X可以嵌套在矩形Y里，就从X到Y连一条有向边。这个有向图是无环的，因为一个矩形无
法直接或间接地嵌套在自己内部。换句话说，它是一个DAG。这样，所要求的便是DAG上
的最长路径。

代码

// 动态规划问题是逆向思考的
// dp(i)表示从序号i出发的最长路径
int dp(int i) {
    int& ans = d[i];
    // 为了不浪费了劳动力，如果d[i]被确定过，则直接返回
    if(ans > 0) return ans;
    ans = 1;
    // i->j有边,表示i能走向j，d[i]则为ans和d[j]+1的最大值
    for(int j = 1; j <= n; j＋＋)
        if(G[i][j]) ans = max(ans, dp(j)＋1);

    // 经过上述步骤，d[i]就确定了不会再改变了
    return ans;
}
int d[n];
memset(d, 0, sizeof(d));

for(int i = 1; i<=n; ++i){
    d[i] = dp(i);
}

// 选出最大的d[max] 然后 print_ans(max)
void print_ans(int i) {
    printf("％d ", i);
    for(int j = 1; j <= n; j++) if(G[i][j] && d[i] == d[j]+1){
        print_ans(j);
        break;
    }
}

// 选出最大的d[max] 然后 print_ans(max)
// 打出所有最长路径
void print_ans(vector<int> vec) {
    // printf("％d ", i);
    int ok = 1;
    for(int j = 1; j <= n; j++) if(G[vec.back()][j] && d[vec.back()] == d[j]+1){
        ok = 0;
        vec.push_back(j);
        print_ans(vec);
        // break;
    }
    if(ok){
        for(auto i = vec.begin(); i!=vec.end(); ++i)
            cout<<vec[i];
    }
}

硬币问题

硬币问题。有n种硬币，面值分别为V1, V2, …, Vn，每种都有无限多。给定非负整数S，
可以选用多少个硬币，使得面值之和恰好为S？输出硬币数目的最小值和最大值。
1≤n≤100，0≤S≤10000，1≤Vi≤S。

HINt

此问题尽管看上去和嵌套矩形问题很不一样，但本题的本质也是DAG上的路径问题。将
每种面值看作一个点，表示“还需要凑足的面值”，则初始状态为S，目标状态为0。若当前在
状态i，每使用一个硬币j，状态便转移到i－Vj。
这个模型和上一题类似，但也有一些明显的不同之处：上题并没有确定路径的起点和终
点（可以把任意矩形放在第一个和最后一个），而本题的起点必须为S，终点必须为0；点固
定之后“最短路”才是有意义的。在上题中，最短序列显然是空（如果不允许空，就是单个矩
形，不管怎样都是平凡的），而本题的最短路却不容易确定。

代码

// 最长路
int dpa(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, dpa(S-V[i])＋1);
    return ans;
}

// 最短路
int dpi(int S){
    // 判重是为了不浪费成果
    if(vis[S]) return d[S];
    vis[S] = 1;
    int& ans = d[S];
    ans = INF;
    if(S=0) ans = -(1<<30);
    for(int i = 1; i <= n; i＋＋) if(S >= V[i]) ans = min(ans, dpi(S-V[i])＋1);
    return ans;
}

memset(vis, 0, sizeof(vis));

// 最短和最长
minv[0] = maxv[0] = 0;
for(int i = 1; i <= S; i＋＋){
    minv[i] = INF; maxv[i] = -INF;
}

// 状态流的方向为S->0，所以外层是1->S;为了保证计算i时，i-V[j]已经被计算
// 参考算法小计B2 18-5-3
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;
        }
}