—— Summon, Light!
0%

HHUACM 寒假专题 动态规划

发表于 更新于 Valine：

F - 数塔

经典问题，数塔。
使用动态规划解决问题的（最重要）前提是：

  1. 问题具有最优子结构
  2. 最优子结构的状态可以记录


例如上图中，以第二层$12$为顶层的数塔就是一个最优子结构。
再回到原来的顶层，想得到最终的结果只需要知道第二层两个子结构能得到的最大和，这是可记录的。
所以，我们从底层往顶层进行动态规划就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;

int a[111][111];

int main()
{
    int T,n;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=i;j++) {
                scanf("%d",&a[i][j]);
            }
        }
        for (int i=n-1;i>=1;i--) {
            for (int j=1;j<=i;j++) {
                a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
            }
        }
        printf("%d\n",a[1][1]);
    }
    return 0;
}

G - 免费馅饼

可以发现时刻的范围不是很大，把每个时刻看作每一层，这个问题就是三条边的数塔。
代码中平移一下是为了避免越界问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int dp[N][13];

int main()
{
    int n;
    while (scanf("%d",&n),n) {
        memset(dp,0,sizeof(dp));
        int m=0;
        for (int i=1;i<=n;i++) {
            int x,t;
            scanf("%d%d",&x,&t);
            ++dp[t][x+1];
            m=max(m,t);
        }
        for (int i=m;i>=0;i--) {
            for (int j=1;j<=11;j++) {
                dp[i][j]+=max(max(dp[i+1][j-1],dp[i+1][j]),dp[i+1][j+1]);
            }
        }
        printf("%d\n",dp[0][6]);
    }
    return 0;
}

A - 饭卡

首先排除余额已经少于$5$的情况，然后分为$m-5$和$5$两部分，前面的$m-5$是个01背包问题，后面的$5$用来买最后一次。若用$dp(x)$表示$x$能买到的最大价值，那么答案为$m-dp(m-5)-a_i (1\le i\le n)$。
可以证明，最后买最贵的是最优的。比较复杂，这里仅通过$m-dp(m-5)-a_p$这个式子简要说明，如果最后买的不是最贵的，即 $p’ \neq p$：

  • $a_{p’}\le a_{p}$
  • 背包的物品集合加入了一个体积大的，去掉了一个体积小的；又有价值跟体积的值相等，所以$dp’(m-5)\le dp(m-5)$

两个减数都减小，最后的结果只会变大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const int N=1100;
int a[N],dp[N];

int main()
{
    int n,m;
    while (scanf("%d",&n),n) {
        for (int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        scanf("%d",&m);
        if (m<5) {
            printf("%d\n",m);
        } else {
            int p=max_element(a+1,a+n+1)-a;
            m-=5;
            memset(dp,0,sizeof(dp));
            for (int i=1;i<=n;i++) {
                if (i==p) continue;
                for (int j=m;j>=a[i];j--) {
                    dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
                }
            }
            printf("%d\n",m+5-dp[m]-a[p]);
        }
    }
    return 0;
}

B - Piggy-Bank

已知存钱罐的确切重量，问最小可能价值。是恰好型的完全背包。
稍微讲一下完全背包一维的转移方程：
$$dp(j)=max(dp(j),dp(j-w_i)+v_i)$$ $j$从小到大枚举时，由于之前的$dp$值已经更新过了，就直接达到了无限个物品的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;

const int M=10010;
const int INF=0x3f3f3f3f;
int dp[M];

int main()
{
    int T,n,m;
    scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        m-=n;
        memset(dp,INF,sizeof(dp));
        dp[0]=0; scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            int p,w;
            scanf("%d%d",&p,&w);
            for (int j=w;j<=m;j++) {
                dp[j]=min(dp[j],dp[j-w]+p);
            }
        }
        if (dp[m]==INF) {
            puts("This is impossible.");
        } else {
            printf("The minimum amount of money in the piggy-bank is %d.\n",dp[m]);
        }
    }
    return 0;
}

C - Investment

给出本金、很多种债券和各自的利息，问$y$年以后最多能有多少钱，抽象一下就是做$y$次完全背包。
但是这题里面容量太大了做不了完全背包，所以题目里又给了一个条件，债券的价格都是$1000$的整数倍，那么直接把本金除以$1000$当作背包容量就行了，重复做$y$次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;

int w[22],v[22];
int dp[50000];

int main()
{
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,M,Y;
        scanf("%d%d",&M,&Y);
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            scanf("%d%d",&w[i],&v[i]);
            w[i]/=1000;
        }
        while (Y--) {
            int m=M/1000;
            memset(dp,0,sizeof(dp));
            for (int i=1;i<=n;i++) {
                for (int j=w[i];j<=m;j++) {
                    dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
                }
            }
            M+=dp[m];
        }
        printf("%d\n",M);
    }
    return 0;
}

D - Common Subsequence

经典问题，最长公共子序列。
子串与子序列
设$C(i,j)$为$x_{1\dots i}$和$y_{1\dots j}$的最长公共子序列的长度，那么有：
$$\large C(i,j)=\begin{cases}
0 & \text{$i=0$ or $j=0$} \\
C(i-1,j-1)+1 & i,j\gt 0, x_i=y_j \\
max(C(i,j-1),C(i-1,j)) & i,j \gt 0, x_i\neq y_j
\end{cases}$$ 第一种情况很好理解。第二种情况就是$x_i$和$y_j$用来匹配了，所以等于了这两个都不用的情况$C(i-1,j-1)$加$1$。第三种情况就是不用$x_i$或者不用$y_j$取一个最大值。
其实第三种是最基本的情况，但是由于$max(C(i,j-1),C(i-1,j))$不会比$C(i-1,j-1)+1$更优（为什么？），所以第二种情况中可以不考虑第三种。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

char a[1010],b[1010];
int dp[1010][1010];

int main()
{
    while (scanf("%s%s",a+1,b+1)!=EOF) {
        int n=strlen(a+1);
        int m=strlen(b+1);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                if (a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        printf("%d\n",dp[n][m]);
    }
    return 0;
}

E - Max Sum

经典问题，最大子列和。（连续子序列，相当于子串）
状态转移方程也比较简单：
$$dp(i)=max(dp(i-1)+a[i],a[i])=max(dp(i-1),0)+a[i]$$ 分别对应两种情况：

  1. 接在上一次序列的后面
  2. 开始一个新的序列

输出的字典序最小意味着左端点和右端点都要最小。如果先记录右端点再反向计算左端点，那么：

  • $dp$值相等时，右端点不被更新
  • 和相等时，左端点要被更新

当然也有其它的记录方法，比如利用数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>
using namespace std;

const int N=100010;
const int INF=1<<28;
int a[N],f[N];

int main()
{
    int T,n,cas=0;
    scanf("%d",&T);
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            scanf("%d",&a[i]);
        }
        int ans=-INF,p,q;
        for (int i=1;i<=n;i++) {
            f[i]=max(f[i-1],0)+a[i];
            if (f[i]>ans) {
                ans=f[i];
                q=i;
            }
        }
        int now=0;
        for (int i=q;i>=1;i--) {
            now+=a[i];
            if (now==ans) p=i;
        }
        printf("Case %d:\n",++cas);
        printf("%d %d %d\n",ans,p,q);
        if (T) puts("");
    }
    return 0;
}

H - 不要62

常见$dp$类型：数位$dp$。可以使用数位$dp$的$dfs$型模板，原理自行查阅。
ps. 这题数据量比较小，可以预处理$O(1)$回答，但是大家还是要好好学习数位$dp$滴。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int D=22;
int dig[D];
ll f[D][10][2];

ll dfs(int pos,int pre,int fg,int limit)
{
    if (pos<0) return fg==0;
    if (!limit&&f[pos][pre][fg]!=-1) {
        return f[pos][pre][fg];
    }
    ll res=0;
    int last=limit?dig[pos]:9;
    for (int i=0;i<=last;i++) {
        res+=dfs(pos-1,i,fg||(pre==6)&&(i==2)||i==4,limit&&(i==last));
    }
    if (!limit) f[pos][pre][fg]=res;
    return res;
}

ll solve(ll n)
{
    int len=0;
    while (n) {
        dig[len++]=n%10;
        n/=10;
    }
    return dfs(len-1,-1,0,1);
}

int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        if (!n&&!m) break;
        memset(f,-1,sizeof(f));
        printf("%lld\n",solve(m)-solve(n-1));
    }
    return 0;
}

I - Unidirectional TSP

常见$dp$类型：网格图$dp$。如果不考虑上下可以穿越，那么转移方程非常简单：
$$dp(i,j)=min(dp(i-1,j-1),dp(i,j-1),dp(i+1,j-1))$$ 上下可以穿越时，需要根据$i$的值特殊处理一下，代码里用的是三目表达式。
因为题目要求输出路径，所以用$a_i$储存前一列可以转移过来的行号，又因为题目里要求字典序最小，所以先排个序，之后按照顺序更新，并约定值相等的不能更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
using namespace std;

const int N=110,INF=1<<28;
int dp[N][N],pre[N][N];

int main()
{
    int n,m;
    while (scanf("%d%d",&n,&m)!=EOF) {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                scanf("%d",&dp[i][j]);
            }
        }
        for (int j=1;j<=m;j++) {
            for (int i=1;i<=n;i++) {
                int a[3]={i};
                a[1]=(i==1)?n:i-1;
                a[2]=(i==n)?1:i+1;
                sort(a,a+3);
                int x=INF,y=-1;
                for (int k=0;k<3;k++) {
                    if (dp[a[k]][j-1]<x) {
                        x=dp[y=a[k]][j-1];
                    }
                }
                dp[i][j]+=x;
                pre[i][j]=y;
            }
        }
        int x=INF,y=-1;
        for (int i=1;i<=n;i++) {
            if (dp[i][m]<x) {
                x=dp[y=i][m];
            }
        }
        stack<int> st;
        for (int j=m;j>=1;j--) {
            st.push(y);
            y=pre[y][j];
        }
        bool fi=true;
        while (!st.empty()) {
            if (fi) {
                printf("%d",st.top());
                fi=false;
            } else {
                printf(" %d",st.top());
            }
            st.pop();
        }
        printf("\n%d\n",x);
    }
    return 0;
}

J - DZY Loves Sequences

常见类型：扫一遍预处理。分别求出向左和向右最多可以延伸的长度，然后对于每一个$a_i$：

  • 如果$a_{i-1} + 1 \lt a_{i+1}$，那么$a_i$可以修改为$a_{i-1}$和$a_{i-1}$之间的某个数使得左右两段连接在一起
  • 如果$a_{i-1} + 1 \ge a_{i+1}$，那么$a_i$只能修改为比$a_{i-1}$大或者比$a_{i-1}$小的数，即左长度加一或者右长度加一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

const int N=100010;
int a[N],l[N],r[N];

int main()
{
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d",a+i);
    }
    l[1]=1;
    for (int i=2;i<=n;i++) {
        if (a[i-1]<a[i]) l[i]=l[i-1];
        else l[i]=i;
    }
    r[n]=n;
    for (int i=n-1;i;i--) {
        if (a[i]<a[i+1]) r[i]=r[i+1];
        else r[i]=i;
    }
    int ans=0;
    for (int i=1;i<=n;i++) {
        l[i]=i-l[i]+1;
        r[i]=r[i]-i+1;
        ans=max(ans,max(l[i],r[i]));
    }
    for (int i=1;i<=n;i++) {
        if (a[i-1]+1<a[i+1]) {
            ans=max(ans,l[i-1]+1+r[i+1]);
        } else {
            ans=max(ans,max(l[i-1]+1,r[i+1]+1));
        }
    }
    printf("%d\n",ans);
    return 0;
}
咖啡，亦我所需也