Htto的小站
0%

DP入门

发表于 更新于 分类于 ，

[TOC]

DP入门

摆花优化

普通摆花我们时间复杂度是\(O(nm^2)\)，其实我们可以对这个大大的求和符号进行优化。洛谷的题解我找了半天居然没有介绍这个优化，还是在白书上看见的

\(f(i,j)=\sum\limits_{k=0}^{a_i}{f(i-1,j-k)}=f(i-1,j)+f(i-1,j-1)...+f(i-1,j-a_i)\)

我们观察到

\(f(i,j-1)=\sum\limits_{k=0}^{a_i}{f(i-1,j-k-1)}=f(i-1,j-1)+f(i-1,j-2)...+f(i-1,j-a_i)+f(i-1,j-1-a_i)\)

就这样我们得到了：

\(f(i,j)=f(i,j-1)+f(i-1.j)-f(i-1,j-1-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
#include <iostream>
#include <vector>
using namespace std;
const int maxn=1e4;
const int mod=1000007;
#define int long long
int n,m;
int f[1005][maxn];
int A[maxn];
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>A[i];
    for(int i=0;i<=n;i++)
        f[i][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(j-1-A[i]>=0)
                f[i][j]=f[i][j-1]+f[i-1][j]-f[i-1][j-1-A[i]];
            else 
                f[i][j]=f[i][j-1]+f[i-1][j];
            f[i][j]=(f[i][j]%mod+mod)%mod;
        }
    }
    cout<<f[n][m];
    return 0;
}

LIS优化

我们上次介绍的最长上升子序列，状态转移方程是:

\[ f[i]=max(f[j]+1,1\le j\lt i\;and\;f[i]>f[j]) \]

它的时间复杂度是\(O(N^2)\)的，其实我们有一个更快速的方法。使用lower_bound。

Coins

我们来看一道很像摆花的一道题，多重部分和问题 (POJ1742 -- Coins) ，有n种不同大小的数字\(a_i\)，每种各\(m_i\)个，判断是否可以从这些数字之中选出若干使他们和恰好为K。这题十分类似于摆花。想想该怎么做?

这里我们的状态表示为\(f(i,j)\)，考虑前\(i\)种硬币，刚好加出\(j\)元，第\(i\)种硬币最多还能剩下多少枚。

AC代码:

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 105;
const int maxm = 100005;
int A[maxn];
int C[maxn];
int f[2][maxm];
int n, m;
void solve()
{
    memset(f, -1, sizeof(f));
    for (int i = 1; i <= n; i++)
        scanf("%d", A + i);
    for (int i = 1; i <= n; i++)
        scanf("%d", C + i);
    int cur = 0;
    // cur^1 是我们即将使用到的上一行
    // 显然第一种硬币加到0元还剩C[1]枚，所以f[前一行][0]初始化为0才能触发第一个if
    f[cur][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        cur ^= 1;
        for (int j = 0; j <= m; j++)
        {
            // 只是用前 i-1种就能加出，那么第i种硬币无需使用
            if (f[cur ^ 1][j] >= 0)
                f[cur][j] = C[i];
            // 那我们就先用掉一枚看看，如果还是没法加成j，我们就放弃了，因为你f[cur][j-A[i]]会帮你算完用2枚能不能....
            else if (j - A[i] >= 0 && f[cur][j - A[i]] >= 0)
                f[cur][j] = f[cur][j - A[i]] - 1;
            // 加不成我们就记录为-1，不能是0，因为0的话可能是刚好全用完.
            else
                f[cur][j] = -1;
        }
    }
    int cnt = 0;
    for (int i = 1; i <= m; i++)
    {
        
        if (f[cur][i] != -1)
            cnt++;
    }
    printf("%d\n", cnt);
}
int main()
{
    while (scanf("%d%d", &n, &m) && n && m)
        solve();
    return 0;
}

划分数

有n个无区别的物品，将他们划分成不超过m组，求出划分方法。

样例

1
2
3
4
5
输入:
4 3
输出:
4
(1+1+2,1+3,2+2,4)

我们要设计出状态转移方程让他不重复不遗漏的计数。一个显然的方程

​ \[f(i,j):将i划分为不超过j组的方案\]

​ \[f(i,j)=\sum\limits_{k=0}^j{f(i-1,j-k)}\]

这样的方程会将1+2+1和2+1+1当成两种方案。出现了重复。怎么才能保证不重复不遗漏呢?

我们可以把每组当成盘子，我们要摆东西在上面，我们发现\(i\)个盘子随意摆放可以分成 \(i\)个盘子都要用到的数量加上前\(i-1\)个盘子随意使用的方案数，这两个状态一定不重叠。那么我们该如何每个盘子都用到呢，可以每个盘子都先放一个还剩下\(j-i\)个物品可以随意摆放。状态转移方程 \[ f(i,j)=f(i,j-i)+f(i-1,j) \]

P1280 尼克的任务

题目大意

你一天要在公司呆上n分钟，你会有k个任务需要完成，每个任务都有一个到达时间和持续时间，如果一个任务来了，你是空闲状态，则你必须接其中一个任务。问你最大摸鱼时间。同一个时刻可能会有多个任务！！

这题很很显然的状态是时间\(t\)。

而这里任务是强制的，到了必须接其中一个，除非你在忙。所以我们只要一个t就好了

\(f(t)\)表示从t秒开始最大获得的空闲时间。or 从1到t秒能获得空闲时间?

转移方程

\(f(t)\):从t开始最多有多少空闲时间，t分钟时你是空闲状态 \[ f(t)=\begin{cases} 1+f(t+1) ; free\\ max(f(j)) ;have\\ \end{cases} \]

多重背包

前面我们介绍了0-1背包，和完全背包，多重背包是这两个背包的结合，给定每个物件的数量限制，不想0-1背包限制为1和完全背包无限制。我们来看一道题，背包综合训练

我们可以将多重背包拆分。如果有一种背包能用cnt次，显然的方法是一个一个拆分，将其变成cnt个背包，每个背包只能用一次，这样我们就转化为0-1背包问题了，但是这样做显然很低效，我们还可以考虑二进制拆分。将其拆分为\(1,2,4...2^{n-1},res\) ，\(res\)是cnt减去前面那个公比为2的等比数列的和且不为\(2^n\)。

你会发现拆分的数列中选取一个子序列可以表示从\([0,cnt]\)中的所有整数，显然从\([0,2^n-1]\)的整数都可以很轻松的表示出来。我们观察它去除res的等比数列，它可以当成无符号数编码，最大是\(11111...\) \(n\)个\(1\) 最小是\(00000...\)\(n\)个0。如果要表示\([2^n,cnt]\)之间的数呢，这部分数可以写成\(cnt-k\),就是我们去除整个集合的某些数，而k也可以通过前面的等比数列表示，只不过这次我们是不选他们。这样\(cnt-k\)可以表示到\(cnt-2^n+1\)，而这个数一定小于等于\(2^n-1\)，反证 \[ \begin{align} cnt-2^n+1 & \gt 2^n-1\\ cnt &\ge 2^{n+1}-1 \\ \end{align} \] 如果\(cnt=2^{n+1}-1\)的话，他就可以表示出\(1,2,3...2^{n-1},2^n,0\)了。所以通过二进制拆分可以表示出所有的组合。

AC代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
int T, N;
int get_interval()
{
    int h1, m1, h2, m2;
    scanf("%d:%d %d:%d", &h1, &m1, &h2, &m2);
    int t1 = h1 * 60 + m1, t2 = h2 * 60 + m2;
    return abs(t2 - t1);
}
int f[1005] = {-1};
struct F
{
    int cost, v, cnt;
    bool operator<(const F &f) const
    {
        return v / cost;
    }
} arr[10005];

void input()
{
    T = get_interval();
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        arr[i] = {a, b, c};
    }
}
vector<int> split(int p)
{
    vector<int> vec;
    int a=1;
    while(p>=a)
    {
        vec.push_back(a);
        p-=a;
        a*=2;
    }
    if(p)
        vec.push_back(p);
    return vec;
} 
int solve()
{
    f[0] = 0;
    for (int i = 1; i <= N; i++)
    {
        if (arr[i].cnt == 0)
        {
            for (int t = arr[i].cost; t <= T; t++)
                f[t] = max(f[t], f[t - arr[i].cost] + arr[i].v);
        }
        else
        {
            auto vec=split(arr[i].cnt);
            for (int k = vec.size()-1; k >=0; k--)
                for (int t = T; t >= vec[k]*arr[i].cost; t--)
                {
                    // 这里使用一维的，如果使用滚动数组要小心一点哦。
                    f[t] = max(f[t], f[t - vec[k]*arr[i].cost] + vec[k]*arr[i].v);
                }
        }
    }
    return f[T];
}

int main()
{
    input();
    std::cout << solve() << std::endl;
    return 0;
}

CF1513C: Add One

题目大意

给你一个数字，这个数字每秒钟每个数位会加上1，问一个数\(n\)过了\(m\)秒会有几位。以9为例

1秒10， 2秒21，3秒32，4秒43，5秒54...9秒98，10秒109 11 秒，2110

9过了4秒会有4位

结果要对\(10^9+7\)取模

解题思路

我们很容易发现每个数位都是独立的不会相互影响。这样我们可以想到一个简单的dp

\(f(i,t)\):\(i,(i\le10)\)经过\(t\)秒会有几位。如果\(i+t<10,f(i,t)=1\)，如果\(i+t>=10\)，考虑我们刚好变成10的时候，我们时间还有\(t+i-10\)那么状态转移方程就是\(f(i,t)=f(1,i+t-10)+f(0,i+t-10)\)。

AC代码

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 <iostream>
#include <cstdio>
using namespace std;
const int maxm = 2e6 + 5;
const int mod = 1e9 + 7;
int f[10][maxm];
void init()
{
    for (int i = 0; i < 10; i++)
        f[i][0] = 1;
    for (int j = 1; j < maxm; j++)
    {
        for (int i = 0; i < 10; i++)
            if (i + j < 10)
                f[i][j] = 1;
            else
                f[i][j] = (f[0][i + j - 10] + f[1][i + j - 10]) % mod;
    }
}
int main()
{
    init();
    int kase;
    scanf("%d",&kase);
    while (kase--)
    {
        int n, m;
        scanf("%d%d",&n,&m);
        int res = 0;
        while (n)
        {
            int i = n % 10;
            n /= 10;
            res = (res + f[i][m]) % mod;
        }
        cout << res << "\n";
    }
    return 0;
}

前缀和&&差分

如果给你一个数列，让你快速求出很多区间的和 \[ \begin{align} \sum\limits_{i=l}^r{a_i} \end{align} \]

这里他可能询问好多组区间和，如果用传统的一个for循环累加时间复杂度为\(O(nm)\)，会TLE。

一维前缀和

\[ \begin{align} 令S_i &=\sum\limits_{k=1}^i{a_i} \\ \sum\limits_{i=l}^r{a_i}&=S_r-S_{l-1}\\ \end {align} \]

这样我们维护\(S_i\)就可以用一个减法快速求区间和了。

二维前缀和

现在我们拓展到二维，给你一个矩阵，让你求从\((x_0,y_0)到(x_1,y_1)\)所有元素的和。 \[ \left[ \begin{array}{} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ \end{array} \right] \]

\[ f(i,j)=f(i-1,j)+f(i,j-1)-f(i-1,j-1)+A(i,j) \]

差分

如果要对区间频繁进行修改我们可以差分，比如对\([l,r]\)的数都加上一个值\(x\), 可以设置差分数组\(a_l+=x,a_{r+1}-=x\)，这样求

树形dp

首先你要学会建树，树形dp主要要多练啦，这里给几个我的几道题目笔记

区间DP

区间DP即要从区间方面考虑状态转移，区间DP常常会出现环形，对环形的处理也有一点小小的技巧。

环形处理

题目大意

死机后的小健健被骗买了山寨项链 - 题目 - YCITOJ (merdog.cn)

给你一串数，这些数串成一串项链，让你求得其中一个连续的一部分，使得其和最大，输出最大和。注意这是一个环，我们常常使用双倍数组来处理环。

P1880：石子合并

题目大意

题目传送门

给你\(N\)堆石子，这些石子环形相连，开始每个石子就是一个堆，每个堆上有个数，堆可以两两合并，两堆合并成一堆，就会获得两堆之和的分数。问你最大得分和最小得分。

输入

1
2
4
4 5 9 4

输出

1
2
43
54

  1. 5-9合并 变成了 4 14 4 得14分

  2. 4-14合并变成了 18 4 得32分

  3. 18-4合并变成了 22 得54分。最高分54分，最低分同理。

分析

我们可以先不考虑环形情况，先把他们当作“线性的"那么我们设计状态转移方程

\(f(i,j)\)：从第\(i\)个石子加到第\(j\)个石子最多能得到多少分。

注意区间dp一般首先枚举的是区间长度，然后再枚举起始位置。状态转移方程。 \[ f(i,j)=max\left(f(i,x)+f(x+1,j)+\sum\limits_{i\le k \le j}{a_k}\right) \] 对于环形，我们需要进行环处理

AC代码

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 <iostream>
#include <algorithm>
using namespace std;
const int maxn = 205;
int A[maxn];
int f[maxn][maxn];
int f2[maxn][maxn];
int S[maxn];
int n;
int sum(int i, int j)
{
    return S[j] - S[i - 1];
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> A[i];
        A[i + n] = A[i];
    }
    for (int i = 1; i <= 2 * n; i++)
        S[i] = S[i - 1] + A[i];
    int res = 0;
    int res2 = 0x3f3f3f3f;
    for (int k = 2; k <= n; k++)
        for (int i = 1; i + k - 1 <= 2 * n; i++)
        {
            int j = i + k - 1;
            f2[i][j] = 0x3f3f3f3f;
            for (int x = i; x + 1 <= j; x++)
            {
                f[i][j] = max(f[i][j], f[i][x] + f[x + 1][j] + sum(i, j));
                f2[i][j] = min(f2[i][j], f2[i][x] + f2[x + 1][j] + sum(i, j));
                res = max(res, f[i][j]);
            }
        }
    for(int i=1;i<=n;i++)
        res2=min(res2,f2[i][i+n-1]);
    cout << res2 << endl
         << res << endl;
    return 0;
}

P3146: 248G

题目大意

题目传送门

给你一串数，你可以合并两个相邻的数，合并后的数为这两个数原本的值+1，比如2-2合并就变成了3，问你合并后的最大数是多少。

分析

区间dp状态转移方程当然是从区间考虑啦，这题其实和上题的思路差不多。状态转移方程根据题目来就行 \[ f(i,j)=max(f(i,x)+f(x+1,j)\&\&f(i,x)==f(x+1,j)) \]

AC代码

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 <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=250;
int A[maxn];
// 0 left 1 right
int f[maxn][maxn];

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>A[i];
        f[i][i]=A[i];
    }
    int res=0;
    for(int k=1;k<=n;k++)
        for(int i=1;i+k-1<=n;i++)
        {
            int j=i+k-1;
            for(int x=i;x+1<=j;x++)
            {
                if(f[i][x]==f[x+1][j] && f[i][x]!=0)
                    f[i][j]=max(f[i][j],f[i][x]+1);
            }
            res=max(res,f[i][j]);
        }
    cout<<res<<endl;
    return 0;
}

关路灯

题目大意

P1220 关路灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

有\(n\)盏路灯，分布在一个一维坐标系上，每盏路灯功率都不一样，位置也都不一样。

现在你要关掉所有路灯，已知你步行速度为\(1m/s\),按开关的时间忽略不计。输出你关闭所有路灯所消耗的最小功耗。

输入

1
2
3
4
5
6
5 3
2 10
3 20
5 20
6 30
8 10

输出

1
270

解题思路

左右端点区间考虑

\(f(i,j,0)\)表示从\([i,j]\)的路灯都已经熄灭，你在左边也就是\(i\)位置

\(f(i,j,1)\) 表示从\([i,j]\)的路灯都已经熄灭，你在右边也就是\(j\)位置

画个图分情况转移即可。

AC代码

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 55;
int n, c;
struct Light
{
    int p;
    int w;
} A[maxn];

int f[maxn][maxn][2];
int S[maxn];
int cost(int i, int j)
{
    return (A[j].p - A[i].p);
}
int main()
{
    cin >> n >> c;
    memset(f, 0x3f, sizeof(f));
    for (int i = 1; i <= n; i++)
        cin >> A[i].p >> A[i].w;
    f[c][c][0] = f[c][c][1] = 0;
    for (int i = 1; i <= n; i++)
        S[i] = S[i - 1] + A[i].w;

    for (int k = 2; k <= n; k++)
        for (int i = 1; i + k - 1 <= n; i++)
        {
            int j = i + k - 1;
            f[i][j][0] = min(f[i + 1][j][0] + cost(i, i + 1) * (S[n] - S[j] + S[i]), f[i + 1][j][1] + cost(i, j) * (S[n] - S[j] + S[i]));
            f[i][j][1] = min(f[i][j - 1][1] + cost(j - 1, j) * (S[n] - S[j - 1] + S[i - 1]), f[i][j - 1][0] + cost(i, j) * (S[n] - S[j - 1] + S[i - 1]));
        }
    cout << min(f[1][n][0], f[1][n][1]);
    return 0;
}

合唱队

题目大意

题目传送门

给你一个数组(队形)，让你用一下规则对该数列重新排序。

  • \(a_1\)直接放入新数组
  • \(a_i > a_{i-1}\)，将\(a_i\)新插入新数组末尾，否则插入新数组之前。

新数组我们成为理想队形。

现在给你（新数组）理想队形，让你求出有多少初始数组能形成该理想队形。

解题思路

这题和上次类似，都是从区间两端考虑。

对于理想队形的子段\([l,r]\)的解\(f(l,r)\)，因为无法确定初始队形最后一个元素在左边还是右边。那么我们转移到更长的父区间时就无法进行比较，那我们就再加一个状态，记录初始队形最后一个元素加在了左边还是右边即可。然后按照题意转移即可

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
const int maxn = 1e3 + 5;
const int mod = 19650827;
using namespace std;
int A[maxn];
int n;
int f[maxn][maxn][2];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> A[i];
        f[i][i][0]  = 1;
    }
    for (int k = 2; k <= n; k++)
        for (int i = 1; i + k - 1 <= n; i++)
        {
            int j = i + k - 1;
            if (A[i] < A[i + 1])
                f[i][j][0] += f[i + 1][j][0];
            if (A[i] < A[j])
                f[i][j][0] += f[i + 1][j][1];
            if (A[j] > A[i])
                f[i][j][1] += f[i][j - 1][0];
            if (A[j] > A[j - 1])
                f[i][j][1] += f[i][j - 1][1];
            
            f[i][j][0] %= mod;
            f[i][j][1] %= mod;
        }
    cout << (f[1][n][0] + f[1][n][1]) % mod << endl;
    return 0;
}

数位DP

不要六二

题目大意：

如果一个数中出现了4或者62连在一起，我们成为它为不吉利的数，否则为吉利的数

选出从n到m中吉利数的数量。

解题思路:

这类满足某种条件的数字的数量可以尝试使用数位DP，假如n=1, m=5432

我们发现1xxxx, 2xxx和3xxx的吉利数量是一样的，我们可以把它当作同一个状态。

而5xxx却不是因为5它后面一位最多只能取到4，所以我们需要做限制，如果被限定了，下面一个数位只能取到我们输入的数位。

数位DP是一个记忆化搜索大概像这样

1
int dfs(int pos,int last,bool limit);

pos: 是当前处理的数位的位置

last:上一个数位的值

limit: 当前pos是否被限制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int A[8], cnt, dp[8][12][2];

int dfs(int pos, int last, bool limit)
{
    int &ans = dp[pos][last][limit];

    if (pos == cnt)
        return ans = 1;
    if (ans != -1)
        return ans;

    ans = 0;
    for (int v = 0; v <= (limit ? A[pos] : 9); v++)
    {
        if (last == 6 && v == 2 || v == 4)
            continue;
        ans += dfs(pos + 1, v, limit && v == A[pos]);
    }
    return ans;
}

这一题让你求出从n到m之间的符合条件的数，而这个dfs只能求出从1到n，我们可以将两个都求一下如果\(f(n)\)表示从1到n符合条件的数，最后就是求\(f(m)-f(n-1)\)

AC代码:

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
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int A[8], cnt, dp[8][12][2];

int dfs(int pos, int last, bool limit)
{
    int &ans = dp[pos][last][limit];

    if (pos == cnt)
        return ans = 1;
    if (ans != -1)
        return ans;

    ans = 0;
    for (int v = 0; v <= (limit ? A[pos] : 9); v++)
    {
        if (last == 6 && v == 2 || v == 4)
            continue;
        ans += dfs(pos + 1, v, limit && v == A[pos]);
    }
    return ans;
}

int f(int x)
{
    cnt = 0;
    memset(dp, -1, sizeof(dp));
    memset(A, 0, sizeof(A));
    while (x)
        A[cnt++] = x % 10, x /= 10;
    reverse(A, A + cnt);
    return dfs(0, 11, true);
}
int main()
{
    int x, y;
    while (cin >> x >> y && (x || y))
    {
        cout << f(y) - f(x - 1) << endl;
    }
    return 0;
}

数字计数

题目大意:

给定两个正整数 a 和 b，求在 \([a,b]\) 中的所有整数中，每个数码(digit)各出现了多少次。

解题思路:

这一题我们思路和上面一题类似，对于每个数字我们都单独跑一下dfs，要计算0时可以有前导0比如0001，他有3个前导0（我们存数位从高位存到低位），不应该计入结果，所以我们我们还需要引入一个lead，来标记这是不是前导零，处理方法和limit 差不多，如果还没遇到过其他数位lead为true，否则，lead为false。如果当前要计算的数字不是0，lead一开始就设为false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int digit;
int dfs(int pos, int dcnt, bool limit, bool lead)
{
    if (pos == cnt)
        return dcnt;
    int &ans = dp[pos][dcnt][limit][lead];
    if (ans != -1)
        return ans;
    ans=0;
    for (int v = 0; v <= (limit ? A[pos] : 9); v++)
    {
        if (v == 0 && lead)
            ans += dfs(pos + 1, dcnt, limit && v == A[pos], lead);
        else
            ans += dfs(pos + 1, dcnt + (v == digit), limit && v == A[pos], false);
    }
    return ans;
}

digit: 我们当前要计算的数字出现了多少次

代码应该挺清晰的吧。

AC 代码:

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int maxn = 22;
int A[maxn], cnt, dp[maxn][12][2][2];
int digit;
int dfs(int pos, int dcnt, bool limit, bool lead)
{
    if (pos == cnt)
        return dcnt;
    int &ans = dp[pos][dcnt][limit][lead];
    if (ans != -1)
        return ans;
    ans=0;
    for (int v = 0; v <= (limit ? A[pos] : 9); v++)
    {
        if (v == 0 && lead)
            ans += dfs(pos + 1, dcnt, limit && v == A[pos], lead);
        else
            ans += dfs(pos + 1, dcnt + (v == digit), limit && v == A[pos], false);
    }
    return ans;
}
int f(int x)
{
    memset(dp, -1, sizeof(dp));
    memset(A, 0, sizeof(A));
    cnt = 0;
    while (x)
        A[cnt++] = x % 10, x /= 10;
    reverse(A, A + cnt);
    return dfs(0, 0, true, true);
}
signed main()
{
    int x, y;
    cin >> x >> y;
    for (digit = 0; digit <= 9; digit++)
    {
        int l = f(x-1),r=f(y);
        cout<<r-l<<" ";
    }
    return 0;
}

最大异或之和

题目大意:

从\([l,r]\)中选出一对数\((x,y)\)，使得\(x\oplus y\)的值最大。

解题思路:

数位DP不仅可以求数字计数类问题，也可以解决很多二进制按位运算问题。

这题有道很显然的贪心，只要每位贪心每位凑出0-1就行。用数位dp的话就从高位到低位依次考虑。

一般数位dp都有两个limit, limitl , limit r但是之前的问题因为是计数问题可以用\(f(r)-f(l-1)\)所有我们只用到了一个limit，而这一题，我们不能通过上面简单的相减得到结果。

正确的方法是对于每个数都整个limitl,limitr 这样我们就有4个limit

1
int dfs(int p, bool l1, bool r1, bool l2, bool r2);

其他方法和上面的题目差不多，只不过这个需要二重循环，枚举两个数的p数位，然后异或，取最大的一个。

AC代码:

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
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long
using namespace std;
const int maxn = 65;
int cnt = 0;
int L[maxn], R[maxn];
int dp[maxn][2][2][2][2];

int dfs(int p, bool l1, bool r1, bool l2, bool r2)
{
    if (p == cnt)
        return 0;
    int &ans = dp[p][l1][r1][l2][r2];
    if (ans != -1)
        return ans;
    ans = 0;
    for (int i = (l1 ? L[p] : 0); i <= (r1 ? R[p] : 1); i++)
        for (int j = (l2 ? L[p] : 0); j <= (r2 ? R[p] : 1); j++)
        {
            ans = max(ans, ((i ^ j) << (cnt - p-1)) +
                               dfs(p + 1, l1 && i == L[p], r1 && i == R[p], l2 && j == L[p], r2 && j == R[p]));
        }
    return ans;
}

int f()
{
    int cnt1 = 0, cnt2 = 0;
    memset(dp, -1, sizeof(dp));
    memset(L, 0, sizeof(L));
    memset(R, 0, sizeof(R));

    int x, y;
    cin >> x >> y;
    while (x)
        L[cnt1++] = x & 1, x >>= 1;
    while (y)
        R[cnt2++] = y & 1, y >>= 1;
    cnt = max(cnt1, cnt2);
    reverse(L, L + cnt);
    reverse(R, R + cnt);

    return dfs(0, 1, 1, 1, 1);
}
signed main()
{
    cout << f();
    return 0;
}

Sum of log

该题来自第45届ICPC上海C题

题目大意:

给定两个非负整数\(X\),\(Y\)计算 \[ \sum\limits_{i=0}^X{\sum\limits_{j=[i=0]}^Y{[i\&j=0]\lfloor\log_2{(i+j)+1)}\rfloor}} \]

  • & 指的是按位与
  • \([A]\)：当A为真时\([A]\)=1，否则为0

解题思路:

这题应该很裸吧，和上面一题，关于二进制，我们观察\(log_2(i+j)+1\) 等于\(i,j\)位数中较大的加一，因为当\(i\&j=0\)时两个数0-1是错开的，\(i+j\le11111...\)这样的话，状态应该为:

  • pos: 当前的数位
  • max_bit: 最高位的位置
  • limit1:对第一个数限制
  • limit2:对第二个数限制

如果全是前导0的话可以通过max_bit 和pos的关系确定

TLE代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
const int maxn = 31;
const int mod = 1e9 + 7;
int cnt;
int dp[maxn][maxn][2][2];
int X[maxn], Y[maxn];

int dfs(int pos, int max_bit, int limit1, int limit2)
{
    if (max_bit == 0)
        return 0;
    if (pos == cnt)
        return max_bit;
    int &ret = dp[pos][max_bit][limit1][limit2];
    if (ret != -1)
        return ret;
    ret = 0;
    int ex = (limit1 ? X[pos] : 1);
    int ey = (limit2 ? Y[pos] : 1);
    for (int i = 0; i <= ex; i++)
    {
        for (int j = 0; j <= ey; j++)
        {
            if (i + j == 0 && max_bit == cnt-pos)
            {
                ret += dfs(pos + 1, max_bit - 1, limit1 && (i == X[pos]), limit2 && (j == Y[pos]));
                ret %= mod;
            }
            else if ((i & j) == 0)
            {
                ret += dfs(pos + 1, max_bit, limit1 && (i == X[pos]), limit2 && (j == Y[pos]));
                ret %= mod;
            }
        }
    }
    return ret;
}
int f(int x, int y)
{
    cnt = 0;
    int x_cnt = 0, y_cnt = 0;
    memset(dp, -1, sizeof(dp));
    memset(X, 0, sizeof(X));
    memset(Y, 0, sizeof(Y));
    while (x)
        X[x_cnt++] = x & 1, x >>= 1;
    while (y)
        Y[y_cnt++] = y & 1, y >>= 1;
    cnt = max(x_cnt, y_cnt);
    reverse(X, X + cnt);
    reverse(Y, Y + cnt);
    return dfs(0, cnt, 1, 1);
}
signed main()
{
    int T;

    scanf("%d", &T);
    while (T--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        printf("%d\n", f(x, y));
    }
    return 0;
}

其实我感觉这个数据量勉强能过吗，然后就TLE QWQ，还好没打上海赛区，不然就是队友数量-3，时间 -2h。更优的方法是压缩掉一维max_bit，然后记录方案数，用一个全局变量累加方案数*最高位。

当从前导0变成非0的时候，我们记录一下计数，这样才能保证不重复

AC代码:

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
#define int long long
const int maxn = 31;
const int mod = 1e9 + 7;
int cnt;
int dp[maxn][maxn][2][2];
int X[maxn], Y[maxn];
int ans = 0;
int dfs(int pos, int limit1, int limit2, bool zero)
{
    if (pos == cnt)
        return 1;
    int &ret = dp[pos][limit1][limit2][zero];
    if (ret != -1)
        return ret;
    ret = 0;
    int ex = (limit1 ? X[pos] : 1);
    int ey = (limit2 ? Y[pos] : 1);
    int tot = 0;
    for (int i = 0; i <= ex; i++)
    {
        for (int j = 0; j <= ey; j++)
        {
            if (i & j)
                continue;
            if (zero && (i | j))
            {
                int tmp = dfs(pos + 1, limit1 && (i == ex), limit2 && (j == ey), false);
                tot = (tot + tmp) % mod;
                ret = (ret + tmp) % mod;
            }
            else
            {
                ret += dfs(pos + 1, limit1 && (i == ex), limit2 && (j == ey), zero && (i + j == 0));
                ret %= mod;
            }
        }
    }
    ans = (ans+ (tot * (cnt - pos))) % mod;
    return ret;
}
int f(int x, int y)
{
    cnt = 0;
    ans = 0;
    int x_cnt = 0, y_cnt = 0;

    memset(dp, -1, sizeof(dp));
    memset(X, 0, sizeof(X));
    memset(Y, 0, sizeof(Y));
    while (x)
        X[x_cnt++] = x & 1, x >>= 1;
    while (y)
        Y[y_cnt++] = y & 1, y >>= 1;
    cnt = max(x_cnt, y_cnt);
    reverse(X, X + cnt);
    reverse(Y, Y + cnt);
    dfs(0, cnt, 1, 1);
    return ans;
}
signed main()
{
    int T;

    scanf("%lld", &T);
    while (T--)
    {
        int x, y;
        scanf("%lld%lld", &x, &y);
        printf("%lld\n",f(x,y));
    }
    return 0;
}

通行模板

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
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
#define int long long
const int maxn=33;
// pos , limit
int cnt;
int dp[maxn][2];
int A[maxn];
int dfs(int pos,int limit)
{
    if(pos==cnt)
        return 0; // need to change
    int &ans=dp[pos][limit];
    if(ans!=-1)
        return ans;
    for(int i=0;i<=(limit?A[pos]:9);i++)
    {
        // do sometihng;
    }
    return ans;
}
int f(int x)
{
    cnt=0;
    memset(dp,-1,sizeof(dp));
    while(x){
        A[cnt++]=x%10;
        x/=10;
    }
    reverse(A,A+cnt);
    return dfs(0,true);
}
signed main(){
    return 0;
}

第十二届蓝桥杯国赛居然考了一道数位DP裸题，血赚^_^

参考

^ 部分内容参考了 算法学习笔记(68): - Pecco

^ Sum of Log 优化后的代码参考 [题解]牛客竞赛OJ