算法基础_DP

算法基础_DP

一.dp模型

dp问题模型比较的少,主要包括:

二.分析dp的方法

dp没有固定的模板,主要就是for循环,其中状态的表示和状态的计算是关键理解dp问题的方法:

dp分析方法

1.状态表示

所谓的状态就是一个未知数,需要思考这个问题的状态是几维的,比如背包问题就是二维的,然后每一维表示的是什么。这个是状态表示要做的事情

状态包括集合元素是什么,表示的属性是什么\( (f[i]) \)

2.状态计算

状态计算就是集合的划分问题

三.各个dp模型分析

1.背包问题 – 4个例子

1)01背包

  1. 每件物品最多用一次
  2. n件商品,容量为v的背包
  3. 每件商品都有一个体积v和价值w
  4. 目标:选出若干个商品,使其在背包容量的前提下总价值最大

特点:每件商品最多用一次

分析:

对于01背包中的状态表示:

集合:满足条件的所有的选法,满足的条件是:

  • 只从前i个物品中选
  • 选出来的物品的总体积 \( \leq j \)

属性:集合中所有选法的最大值

思考状态计算:

首先目标是求解:\( f(n, v) \)

如何求解包含i的呢?

首先思考一个东西,某小学某班成绩,小明第一名,由于全部成绩太低,老师给每个人 + 50分,然后小明显然还是第一名

根据这样的思路,考虑包含i的集合的价值,他们都减去i的价值,那么集合的最大价值是不变的, 因此右侧的求解相当于:

从\( 1 – i \)中取容量不超过\( j – v_{i} \)的集合的最大价值

因为没有i,所以其等于从\( 1 – i \)中取

因此为:\( f(i – 1, j – v_{i}) \)

题目:见blog背包九讲,这个主要记录一种新的思考dp的方式

背包九讲: https://guifei0.cn/2019/04/03/bei-bao-jiu-jiang-gf/

2)完全背包

特点:每件商品有无限多个

分析

则状态转移方程为:

f[i, j] = f[i - 1, j - k * v[i]] + k * w[i]

状态规划的时间复杂度计算方法:状态数量 * 计算每一个状态需要的时间(计算数量)

上面的这个就是完全背包的朴素解法:三重循环,\( O(n * V^{2}) \)

完全背包的优化

\( f[i, j] = f[i – 1, j – v[i] * k] + w[i] * k \)

\( f[i, j] = max(f[i – 1, j], f[i – 1, j – v[i] * 1] + w[i] * 1 + f[i – 1, j – v[i] * 2] + w[i] * 2, …) \)

观察可知:\( f[i, j] = max(f[i – 1, j], f[i, j – v[i]] + w[i]) \) — 具体列出来就看出来了

这时候就少了一个循环,时间复杂度为:O(NV)

滚动数组优化同样的删除一维即可,因为恒等式没有意义

01背包和完全背包推出的结果:01逆序,完全背包顺序

3)多重背包

特点:每一个物品的个数不一样,最多\( S_{i} \)个

容易得到:

f[i][j] = max(f[i - 1][j - v[i] * k] + w[i] *k;k = 0, 1, 2, ..., s[i])

朴素方法的代码就很容易写出,考虑优化的问题

多重背包优化:优化是状态转移方程的等价变换

\( f[i, j] = max(f[i – 1, j], f[i – 1, j – v[i] * 1] + w[i] * 1 + f[i – 1, j – v[i] * 2] + w[i] * 2, …, f[i – 1, j – v[i] * s[i]] + w[i] * s[i]) \)

\( f[i, j – v[i]] = max( f[i – 1, j – v[i]], f[i – 1, j – 2 * v[i]] + w[i], …, f[i – 1, j – s[i] * v[i]] + (s[i] – 1) * w[i], f[i – 1, j – (s[i] + 1) * v[i]] + s[i] * w[i]) \)

现在问题就是说:

给定一个数组:\( a_{1}, a_{2}, a_{3}, …, a_{n} \)的最大值Max,求前n – 1项的最大值,显然是不能解的,所以无法采用完全背包的方式进行优化

考虑另外的优化方法,方法是二进制拆分优化,那么这个方法来源是什么qwq,自己理解:

dp的核心就是状态的表示,说白了如果没有状态转移,其实dp就是暴力枚举,dfs,那么核心就是状态表示问题,只要有一种方法能够表示所有状态即可,并且有有效的状态转移方法就行了

多重背包中,比如s[i] = 1023

最简单的表示方式:暴力:0 1 2 … 1023

那么有没有更好的方法??不知道各位小时候玩过读心术纸牌没有(因为小学的时候对这个很感兴趣,推导了一遍这个魔术,所以记忆非常深刻qwq),就是心里面想一个数字,然后看每张卡片(预先写上去的数组)中是否存在,最后表演者只需要将每张卡片中的首个数字相加就行了??为什么?其实就是二进制的方法

由于二进制的原理,显然1 2 3 4 … 512他们的组合可以表示 0 – 1023中的每个数字,那么就可以把1023一组的物品,分为这几组物品,考虑他们取或不取即可(01背包问题)即可,然后考虑非\( 2^{n} \)情况,这个稍微复杂一点

对于0 – S而言,证明其能够由\( 1, 2, 4, …, 2^{k} , C \)其中\( C < 2^{k + 1} \)组合构成

首先\( 0 \sim 2^{k+1} – 1 \)没有疑问,将其同时 + C 可知其为:

\( C \sim 2^{k+1}-1+C \),其中\( S = 2^{k+1}-1+C \)

那么现在问题就是\( 2^{k+1}-1 \sim C \)这个区间是否能够表示其中的任何一个数字

假设无法表示,那么就有:\( C > 2^{k+1} \),与假设不成立,得证

然后多重背包问题就转换成了01背包\( O(N * V * log(S)) \)

简单模板代码具体见:背包九讲,以下为模板:

有 N 种物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。

输入格式

第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数,表示最大价值。

数据范围

\( 0<N≤1000 \)
\( 0<V≤2000 \)
\( 0<vi,wi,si≤2000 \)

提示:

本题考查多重背包的二进制优化方法。

输入样例

4 5
1 2 3
2 4 1
3 4 3
4 5 2

输出样例:

10

AC代码:

贴一个carbon导出的图片,挺好看的,这个插件十分推荐carbon-now-sh

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e5 + 6;

int n, m;
int v[maxn], w[maxn];
int f[maxn];

int main(){
    sd(n), sd(m);
    int cnt = 0;
    for(int i = 1;i <= n;++i){
        int a, b, s;
        sd(a), sd(b), sd(s);
        int k = 1;
        while(k <= s){
            cnt++;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0){
            cnt++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for(int i = 1;i <= n;++i){
        for(int j = m;j >= v[i];--j){
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    }
    cout << f[m] << endl;

    return 0;
}

4)分组背包

特点:同一分组下的物品最多选一个

分组背包就很简单了

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个,同一组内的物品最多只能选一个。
每件物品的体积是 \( v_{ij} \),价值是 \( w_{ij} \),其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大。

输出最大价值。

输入格式

第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。

接下来有 N 组数据:

  • 每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
  • 每组数据接下来有 \( S_{i} \) 行,每行有两个整数 \( v_{ij}, w_{ij} \),用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;

输出格式

输出一个整数,表示最大价值。

数据范围

\( 0<N,V≤100 \)
\( 0<Si≤100 \)
\( 0<v_{ij},w_{ij} ≤100 \)

输入样例

3 5
2
1 2
2 4
1
3 4
1
4 5

输出样例:

8

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e2 + 6;

int n, m;
int v[maxn][maxn], w[maxn][maxn], s[maxn];
int f[maxn];


int main(){
    sd(n), sd(m);
    for(int i = 1;i <= n;++i){
        sd(s[i]);
        for(int j = 0;j < s[i];++j){
            sd(v[i][j]), sd(w[i][j]);
        }
    }
    for(int i = 1;i <= n;++i){
        for(int j = m;j >= 0;--j){
            for(int k = 0;k < s[i];++k){
                if(v[i][k] <= j){
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    cout << f[m] << endl;

    return 0;
}

2.线性dp

1)什么是线性dp

递推方程有明显的线性关系,动态规划中的每一个状态都是一个多维的状态,有一个求解的顺序问题,比如背包问题就是一个二维的状态,画出来就是一个二维矩阵,求解过程也是一行行求解,因此背包问题就是线性dp

所有的递推关系具有一定的线性关系,就是线性dp

2)dp基础问题 – LIS,LCS,数字三角形

LIS:最长上升子序列 及其 二分贪心优化

LCS:最长公共子序列

数字三角形:数塔,dp中的hello world

这个都比较简单,见之前的blog:https://guifei0.cn/2019/04/02/dp-jichu-is-lcs-shuzisanjiaoxing/

主要说一下如何采用上述说的dp方法来分析这些问题,以数字三角形为例

利用曲线救国的思想,容易得到状态转移方程

\( f[i, j] = max(f[i – 1, j – 1] + a[i, j], f[i – 1, j] + a[i, j]) \)

同样的对于LIS:

集合的划分是按照比如当前第i个数结尾的序列的集合,这些序列的前面i – 1位置是什么?设为\( a_{j} \),那么必然有:

\( a_{j} < a_{i} \)

那么转移方程很容易得到为:

\( f[i] = max(f[j] + 1), a_{j} < a_{i}, j = 0, 1, 2, …, i – 1 \)

时间复杂度:\( O(N^{2}) \)

LCS问题:这个问题很重要!!!!!!!!!!体现了dp中max属性的一种非常重要的一点性质

PS:本人表达的不一定很清晰qwq,所以主要用来本人的记录,各位大佬轻虐~~~

进入正题:对于4种情况而言,00和11的都比较容易qwq,而对于01和10的两种情况呢?

首先思考一下01是不是\( f[i – 1, j] \)?

显然不是!!!,为什么?

因为01的情况表示的选了b[j],没有选a[i],而\( f[i – 1, j] \)表示的是:

所有在第一个序列的前i – 1种的字母中出现,且在第二个序列中的前j个字母出现的子序列,显然的这个范围更大

那么如何表示01呢????

首先再说一下dp的问题:dp不考虑方程的前提下,就是暴力枚举, 利用dp是对枚举的一种优化,方程的好坏决定优化的好坏,那么dp做的事情就是只枚举目前应该枚举的, 不应该枚举的,不枚举,这是dp的思路,显然的dp必须包括所有情况,大块说就是:包括处理的部分和不处理的部分,总体应该是所有状态

因此dp满足:不遗漏,大多数需要不重复

那么有:很重要!!!

那么考虑这个问题,01状态无法表示,那么能不能用较大的状态来表示呢?对于Max而言,显然是可以的,因为Max(A, B, B, C)和Max(A, B, C)是一样的,对于Max而言,子状态的重复对结果是没有影响的,所以无所谓范围大了,只要包括01的状态就行,所以可以用\( f[i – 1, j] \)来表示01的状态来计算最大值

同样的,用这种情况,就包含了00情况,所以00也不用求了,所以问题就是只需要求解01,10,11就行了

因此:对于Max属性而言,子状态可以重复

PS:做dp一定不能想当然求解,如果经常蒙对的话,很多dp问题就不容易求解出来,一定要理解状态是怎么划分的,为什么这样划分,这样划分如何进行计算等等问题。

代码就很简单啦,附上代码:

#include <iostream>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e3 + 6;

int n, m;
char a[maxn], b[maxn];
int f[maxn][maxn];

int main(){
    sd(n), sd(m);
    scanf("%s%s", a + 1, b + 1);
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            if(a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
        }
    }
    cout << f[n][m] << endl;

    return 0;
}

这个地方注意,不能用int的方式读入,因为int是4个字节,这样每四个物理单元读入一个,相当于就是输入的每四个字符会读入到数组的一个元素中,其他都是0,所以是不对的。

3)记录LIS的方案 – 最大序列

对于LIS问题,不仅要算出结果,而且给出最大序列是什么

和图论中的类似,用数组g来记录其前面是什么:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e3 + 6;

int n;
int arr[maxn], f[maxn], g[maxn];
stack<int > st;

int main(){
    sd(n);
    for(int i = 1;i <= n;++i) sd(arr[i]);
    for(int i = 1;i <= n;++i){
        f[i] = 1;
        g[i] = 0;
        for(int j = 1;j < i;++j){
            if(arr[j] < arr[i]){
                if(f[i] < f[j] + 1){
                    f[i] = f[j] + 1;
                    g[i] = j;
                }
            }
        }
    }
    int k = 1;
    for(int i = 1;i <= n;++i){
        if(f[k] < f[i]){
            k = i;
        }
    }
    cout << f[k] << endl;
    while(!st.empty()) st.pop();
    for(int i = 0, len = f[k];i < len;++i){
        st.push(arr[k]);
        k = g[k];
    }
    while(!st.empty()){
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;

    return 0;
}

3.区间dp问题

什么是区间dp问题:所谓区间dp问题,就是所有的状态都是一个区间

模板题目 – 石子合并:

设有N堆石子排成一排,其编号为1,2,3,…,N。

每堆石子有一定的质量,可以用一个整数来描述,现在要将这N堆石子合并成为一堆。

每次只能合并相邻的两堆,合并的代价为这两堆石子的质量之和,合并后与这两堆石子相邻的石子将和新堆相邻,合并时由于选择的顺序不同,合并的总代价也不相同。

例如有4堆石子分别为 1 3 5 2, 我们可以先合并1、2堆,代价为4,得到4 5 2, 又合并 1,2堆,代价为9,得到9 2 ,再合并得到11,总代价为4+9+11=24;

如果第二步是先合并2,3堆,则代价为7,得到4 7,最后一次合并代价为11,总代价为4+7+11=22。

问题是:找出一种合理的方法,使总的代价最小,输出最小代价。

输入格式

第一行一个数N表示石子的堆数N。

第二行N个数,表示每堆石子的质量(均不超过1000)。

输出格式

输出一个整数,表示最小代价。

数据范围

\( 1≤N≤300 \)

输入样例:

4
1 3 5 2

输出样例:

22

分析:

区间dp就是状态表示的时候表示的是一个区间

对于目前左边为[i, k]右边为[k + 1, j]的集合。同样用曲线救国的方法,先减去合并这两堆石子的代价,然后求出Min,再加上,即为:

\( f[i, j] = min(f[i, k] + f[k + 1, j] + s[j] – s[i – 1]), k = i + 1, …, j – 1\),其中s为前缀和

时间复杂度:\( O(n ^ {3}) \)

AC代码:

顺序问题,区间dp问题一般枚举顺序就是:枚举区间长度,然后枚举起始点,然后枚举分界线

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 3e2 + 6;

int n;
int s[maxn], f[maxn][maxn];

int main(){
    sd(n);
    for(int i = 1;i <= n;++i){
        sd(s[i]);
    }
    for(int i = 2;i <= n;++i){
        s[i] += s[i - 1];
    }
    for(int len = 2;len <= n;++len){
        for(int i = 1;i + len - 1 <= n;++i){
            int l = i, r = i + len - 1;
            f[l][r] = inf;
            for(int k = l;k < r;++k){
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            } 
        }
    }
    cout << f[1][n] << endl;

    return 0;
}

记忆化搜索会更加简单,后面会说记忆化搜索,记忆化搜索会比for循环多常数级别的复杂度

石子合并会延申一道题目:dp套dp问题,之后会写blog说,比较复杂

4.计数类dp

整数划分

一个正整数n可以表示成若干个正整数之和,形如:\( n=n_{1}+n_{2}+…+n_{k} \),其中\( n_{1} ≥ n_{2} ≥ … ≥n_{k}, k ≥ 1 \)

我们将这样的一种表示称为正整数n的一种划分。

现在给定一个正整数n,请你求出n共有多少种不同的划分方法。

输入格式

共一行,包含一个整数n。

输出格式

共一行,包含一个整数,表示总划分数量。

由于答案可能很大,输出结果请对\( 10^{9}+7 \)取模。

数据范围

\( 1≤n≤1000 \)

输入样例:

5

输出样例:

7

分析:

这个问题比较的简单,对于当前的i的j个数表示,那么如果最小值为1的话,那么就利用曲线救国的思路,先都减去这个1,然后求数量即可(后面加上1数量不会变)

然后对于最小值 > 1的情况,那么这个方案如何求呢?

同样采用曲线救国的思路,全部都减去1,然后求出方案数量(之后再都加上1),这个要好好理解一下曲线救国思路的精妙,都减去1,为什么不能将最大的两个-1呢?曲线救国是dp中很重要的思路~~(类似映射的关系)

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e3 + 6;
const int mod = 1e9 + 7;

int n;
int f[maxn][maxn];

int main(){
    sd(n);
    f[1][1] = 1;
    for (int i = 2; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
    int res = 0;
    for (int i = 1; i <= n; i ++ ) 
        res = (res + f[n][i]) % mod;

    cout << res << endl;

    return 0;
}

这个题目还有一种完全背包解法也比较简单,简单的记录一下:

物品:\( 1 \sim n),重量和物品编号一致,价值可以默认为方案,每个物品方案可以视为0,初始化方案是1

背包容量:n

将物品放入背包中,不限个数,求价值最大(刚好 == n)

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e3 + 6;
const int mod = 1e9 + 7;

int n;
int f[maxn];

int main(){
    sd(n);
    f[0] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = i; j <= n; j ++ )
            f[j] = (f[j] + f[j - i]) % mod;
    cout << f[n] << endl;

    return 0;
}

5.数位统计dp

计数问题

给定两个整数 a 和 b,求 a 和 b 之间的所有数字中0~9的出现次数。

例如,a=1024,b=1032,则 a 和 b 之间共有9个数如下:

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中‘0’出现10次,‘1’出现10次,‘2’出现7次,‘3’出现3次等等…

输入格式

输入包含多组测试数据。

每组测试数据占一行,包含两个整数 a 和 b。

当读入一行为0 0时,表示输入终止,且该行不作处理。

输出格式

每组数据输出一个结果,每个结果占一行。

每个结果包含十个用空格隔开的数字,第一个数字表示‘0’出现的次数,第二个数字表示‘1’出现的次数,以此类推。

数据范围

\( 0<a,b<100000000 \)

输入样例:

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

输出样例:

1 2 1 1 1 1 1 1 1 1
85 185 185 185 190 96 96 96 95 93
40 40 40 93 136 82 40 40 40 40
115 666 215 215 214 205 205 154 105 106
16 113 19 20 114 20 20 19 19 16
107 105 100 101 101 197 200 200 200 200
413 1133 503 503 503 502 502 417 402 412
196 512 186 104 87 93 97 97 142 196
398 1375 398 398 405 499 499 495 488 471
294 1256 296 296 296 296 287 286 286 247

分析:

做法中最重要最重要的一部分是:分情况讨论qwq,感觉在说废话~~嘤嘤嘤,其实很重要很重要

首先先实现一个函数count(n, x)表示1-n中x出现的次数

那么\( [a, b], x \)就是count(b, x) – count(a – 1, x)类似前缀和

那么如何写count函数?

\( 1 \sim n \)中x出现的次数

思路就是:计算x在每个数的每一位出现的次数

举例求解1在第4位上出现的次数

\( 1 \leq xxx1yyy \leq abcdefg \)

分情况讨论:

  1. \( xxx = 000 \sim abc – 1, yyy = 000 \sim 999, abc * 1000\)
  2. \( xxx = abc \)
    1. \( d < 1, abc1yyy > abc0efg, 0 \)
    2. \( d = 1, yyy = 000 \sim efg, efg + 1 \)
    3. \( d > 1, yyy = 000 \sim 999, 1000 \)

然后累加起来就能够求出1在每一位的次数,同样的方法就能求出来0-9的所有次数了,然后再用前缀和的方法就能求出来了

时间复杂度:10 * 2 * 8 * 10 = 1600

数位dp的核心是:分情况讨论

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e3 + 6;

int get(vector<int> num, int l, int r){
    int res = 0;
    for (int i = l;i >= r;--i) res = res * 10 + num[i];
    return res;
}

int power10(int x){
    int res = 1;
    while (x--) res *= 10;
    return res;
}

int count(int n, int x){
    if (!n) return 0;
    vector<int> num;
    while (n){
        num.push_back(n % 10);
        n /= 10;
    }
    n = num.size();
    int res = 0;
    for (int i = n - 1 - !x;i >= 0;--i){
        if (i < n - 1){
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i);
        }
        if (num[i] == x) res += get(num, i - 1, 0) + 1;
        else if (num[i] > x) res += power10(i);
    }
    return res;
}

int force_count(int n, int x){
    int res = 0;
    for (int i = 1;i <= n;++i){
        for (int j = i; j; j /= 10)
            if (j % 10 == x)
                res ++ ;
    }
    return res;
}

int main(){
    int a, b;
    while (sd(a), sd(b) , a){
        if (a > b) swap(a, b);
        for (int i = 0; i <= 9; i ++ )
            cout << count(b, i) - count(a - 1, i) << ' ';
        cout << endl;
    }

    return 0;
}

6.状态压缩dp

状态压缩的问题在于思维的转换,int与二进制的那种转换

状态压缩的特点:n比较小,最多20

蒙德里安的梦想

求把N*M的棋盘分割成若干个1*2的的长方形,有多少种方案。

例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。

如下图所示:

2411_1.jpg

输入格式

输入包含多组测试用例。

每组测试用例占一行,包含两个整数N和M。

当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。

输出格式

每个测试用例输出一个结果,每个结果占一行。

数据范围

\( 1≤N,M≤11 \)

输入样例:

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例:

1
0
1
2
3
5
144
51205

分析:

仅仅考虑放横向的块,其他的都放入竖向的块,这样的话,就需要保证不能有两个连续的横向的块之间的距离是奇数,因为竖向的块的长度是偶数

用\( f[i, j] \)表示第i列放入横向块的状态j的所有放置方法,属性是:数量

对于状态的计算,首先保证不能有重叠,比如i – 1列在第3行放入了,那么第i列,这一行就不能放入了,还有就是上面说的,横向块之间的距离不能是奇数,用二进制表示每一列的状态,1表示放入,0表示没有放入,那么就是:设当前列的状态为j,前面列的状态为k

  • j & k == 0
  • j | k不存在连续的奇数0

对于不存在连续个奇数0,可以用st数组预处理一下就行了

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 16;
int n, m;
long long f[maxn][1 << maxn];
bool st[1 << maxn];

int main(){
    while (sd(n), sd(m), n || m){
        for (int i = 0;i < 1 << n;++i ){
            int cnt = 0;
            st[i] = true;
            for (int j = 0;j < n;++j)
                if (i >> j & 1){
                    if (cnt & 1) st[i] = false;
                    cnt = 0;
                }
                else cnt ++ ;
            if (cnt & 1) st[i] = false;
        }
        memset(f, 0, sizeof f);
        f[0][0] = 1;
        for (int i = 1;i <= m;++i)
            for (int j = 0;j < 1 << n;++j)
                for (int k = 0;k < 1 << n;++k)
                    if ((j & k) == 0 && st[j | k])
                        f[i][j] += f[i - 1][k];

        cout << f[m][0] << endl;
    }

    return 0;
}

最短Hamilton路径  

给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数n。

接下来n行每行n个整数,其中第i行第j个整数表示点ii到jj的距离(记为a[i,j])。

对于任意的x,y,z,数据保证 \(a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z] \geq a[x, z] \)。

输出格式

输出一个整数,表示最短Hamilton路径的长度。

数据范围

\( 1≤n≤20 \)
\( 0≤a[i,j] \leq 107 \)

输入样例:

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例:

18

分析:

先考虑dfs暴力,显然是(n – 2)!

然后考虑0, 1, 2, 3,答案必然是这两个的最小值

0 -> 1 -> 2 -> 3
0 -> 2 -> 1 -> 3

因此,其实中间的状态不需要考虑,比如对于0到3并且经过1和2的路径,其最小值就是一个固定的值,因此对于题目:

  • 初态:从0开始到0经过0的路径最小值是0
  • 终态:从0开始到n – 1经过0 – n – 1的每个点的路径的最小值
  • 中间状态:从某个点开始到j点经过某些点的路径最小值

发现:其实相关的只有两个东西:

  • 终点是什么
  • 经过了哪些点

用f[state][j]表示终点为j,并且经过state(状态压缩)些点的最小值,则:

初态:\( f[000…001][0] \)

f[1][0]

终态:\( f[111…111][n – 1] \)

f[(1 << n) - 1][n - 1]

中间状态转移:\( f[state][j] \)

对于当前经过state终点为j的状态,可以由中间点(k)来更新,其为到k的最小值 + 从k到j的路径权值,即为:

\( f[state][j] = min(f[state][j], f[state_k][k] + weight[k][j]) \)

state_k是什么呢 ?显然的:不经过j点的哪些路径

因此,状态转移方程就是:

\( f[i][j] = min(f[i][j], f[i – (1 << j)][k] + weight[k][j]) \)

AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e6 + 6;
const int N = 20, M = 1 << 20;
int n;
int f[M][N], weight[N][N];
int main(){
    sd(n);
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            sd(weight[i][j]);
        }
    }
    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;
    
    for(int i = 0;i < 1 << n;++i){
        for(int j = 0;j < n;++j){
            if(i >> j & 1){
                for(int k = 0;k < n;++k){
                    if(i - (1 << j) >> k & 1){
                        f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1] << endl;
    return 0;
}

7.树形dp

树形dp没有背包和线性dp的思维难度大,但是dp的方式会比较的特别,需要适应树形dp的方式,一般树形dp比较简单~~

没有上司的舞会 – 最经典的树形dp问题

Ural大学有N名职员,编号为 \(1 \sim N \)。

他们的关系就像一棵以校长为根的树,父节点就是子节点的直接上司。

每个职员有一个快乐指数,用整数 \(H_{i}\) 给出,其中 \( 1≤i≤N \)。

现在要召开一场周年庆宴会,不过,没有职员愿意和直接上司一起参会。

在满足这个条件的前提下,主办方希望邀请一部分职员参会,使得所有参会职员的快乐指数总和最大,求这个最大值。

输入格式

第一行一个整数N。

接下来N行,第 i 行表示 i 号职员的快乐指数  \(H_{i}\)  。

接下来N-1行,每行输入一对整数L, K,表示K是L的直接上司。

最后一行输入0,0。

输出格式

输出最大的快乐指数。

数据范围

\( 1≤N≤6000 \)
\( −128≤Hi≤127 \)

输入样例:

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

输出样例:

5

分析:

画一个树来理解一下:

这样就得到了状态转移方程,时间复杂度:

每一个状态的计算是儿子的数量,所有的状态加起来就是数的节点个数:\( O(n) \)

因此时间复杂度就是\( O(n) \)

树用邻接表存储,AC代码:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e4 + 6;

int n;
int happy[maxn];
int head[maxn], ver[maxn], Next[maxn], tot;
int f[maxn][2];
bool hash_father[maxn];

void add(int x, int y){
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}

void dfs(int u){
    f[u][1] = happy[u];
    for(int i = head[u];i != -1;i = Next[i]){
        int y = ver[i];
        dfs(y);
        f[u][0] += max(f[y][0], f[y][1]);
        f[u][1] += f[y][0];
    }
}

int main(){
    sd(n);
    for(int i = 1;i <= n;++i) sd(happy[i]);
    memset(head, -1, sizeof head);
    for(int i = 0;i < n - 1;++i){
        int a, b; sd(a), sd(b);
        hash_father[a] = true;
        add(b, a);
    }
    int root = 1;
    while(hash_father[root]) root++;
    dfs(root);
    cout << max(f[root][0], f[root][1]) << endl;

    return 0;
}

8.记忆化搜索

记忆化搜索是采用递归的方式实现动态规划

递归的方式会更加的容易理解

滑雪

给定一个R行C列的矩阵,表示一个矩形网格滑雪场。

矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发,每次可以向上下左右任意一个方向滑动一个单位距离。

当然,一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子:

 1  2  3  4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

在给定矩阵中,一条可行的滑行轨迹为24-17-2-1。

在给定矩阵中,最长的滑行轨迹为25-24-23-…-3-2-1,沿途共经过25个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度,请你找出在该滑雪场中能够完成的最长滑雪轨迹,并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数R和C。

接下来R行,每行包含C个整数,表示完整的二维矩阵。

输出格式

输出一个整数,表示可完成的最长滑雪长度。

数据范围

1≤R,C≤300
0≤矩阵中整数≤10000

输入样例:

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例:

25

分析:

PS:样例是从25开始滑动,最多滑25个格子

递归实现:

#include <bits/stdc++.h>
using ll = long long;
inline int sd(int &n) { return scanf("%d", &n); }
inline int sld(ll &n) { return scanf("%lld", &n); }
const int inf = 0x3f3f3f3f;
const double INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
using namespace std;
const int maxn = 1e3 + 6;

int n, m;
int h[maxn][maxn];
int f[maxn][maxn];

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dp(int x, int y){
    int &v = f[x][y];
    if(v != -1) return v;
    v = 1;
    for(int i = 0;i < 4;++i){
        int a = x + dx[i], b = y + dy[i];
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]){
            v = max(v, dp(a, b) + 1);
        }
    }
    return v;
}

int main(){
    sd(n), sd(m);
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            sd(h[i][j]);
        }
    }
    memset(f, -1, sizeof f);

    int res = 0;
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= m;++j){
            res = max(res, dp(i, j));
        }
    }
    cout << res << endl;

    return 0;
}

记忆化搜索的优点:

从三个方面考虑:

  • 时间复杂度
  • 空间复杂度
  • 代码复杂度:很重要

dp的记忆化搜索的好处就是代码复杂度很低,基本上方程写完之后就可以立马实现,看似代码会长一些,但是逻辑清晰,思路简单,很方便书写

2+

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 + 9 =