小丑西瓜9

这个屌丝很懒，什么也没留下！

热门标签

[做题]动态规划

作者：小丑西瓜9 | 2024-04-04 09:52:50

踩

[做题]动态规划

0.DP前言

下面一系列的线性dp问题更依赖闫氏dp分析法的发挥。

这里记录几条经验：

当状态计算方程中，在遍历时出现了 f[i-1] 的字样，那么数组下标就要从1开始，来防止负数下标和越界。
状态表示，我们划分集合的原则为 “不重不漏”：不重复，不遗漏。
当状态属性要求取 sum 集合的总和时，不重复的原则很重要。

但状态属性取 max/min 集合的最值时，集合间元素发生重复不会影响结果。

举个例子： 1,2,3
- 求最值：max = max(max (1,2) , max (2,3) )。这里2发生了重复，但不影响最大值3的求取。
- 求总和：sum = sum(sum (1,2) , sum(2,3) )。这里2发生了重复，影响了总和的求取（2被加了两次）
状态表示分为三部分：
- 集合的维度：一维数组 f[i] 能求出答案吗？不能的话就用二维数组f[i] [j] ，还不行就三维。
- 集合的表示：每个集合，它的意义是什么？这个意义要能概括题目的所有情况。
- 集合的属性：求sum还是max？属性有时会影响状态计算方程的展开。
一个简单的数学模型：

集合A：a1,a2,a3 … an

集合B：a1+w,a2+2, … an+w

则有：min(A)+w = min(B)

或：min(A) = min(B) - w
C++语言，一秒处理数据大小为 10^{8左右，尽量把复杂度控制在10}7，最多10^8

1.线性DP

数字三角形

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

DP分析

状态表示：

1

状态转移：

朴素做法

#include<iostream>
using namespace std ;
const int N = 510 , INF = 1e9;

int f[N][N];
int a[N][N];
int n;

int main(void)
{
    //初始化数据
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            scanf("%d",&a[i][j]);
        }
    }
    //dp数组赋初值 (下标从1开始，不会产生越界问题。但下标为0的数据要提前赋初值，也就是INF)
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){ //初值范围是[0,i+1] ，左右端点 0和i+1 都会用到。
            f[i][j] = -INF;
        }
    }
    f[1][1] = a[1][1];  //转移方程的初值。
    //状态转移
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j] = max(f[i-1][j]+a[i][j],f[i-1][j-1]+a[i][j]);
        }
    }
    //输出
    int res = -INF;
    for(int i=1;i<=n;i++) res = max(res,f[n][i]);
    cout<<res;
    
}
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

更优雅的写法

#include <bits/stdc++.h>

using namespace std;

const int N = 510;

int f[N][N];
int n;

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> f[i][j];

    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i + 1][j + 1], f[i + 1][j]) + f[i][j];

    cout << f[1][1] << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

该做法是从最下方，向上推。

朴素做法是从第二层，向下推。

一维优化(朴素版本)

 #include <iostream>
#include <algorithm>

using namespace std;

const int N = 510, INF .....................................................................
    = -1e9;

int a[N][N];
int f[N];
int n, m;

int main()
{
    cin >> n;

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= i; j ++)
		cin >> a[i][j];

    for (int i = 0; i <= n + 1; i ++ ) f[i] = INF;

    f[1] = a[1][1];

    for (int i = 2; i <= n; i ++)
        for (int j = i; j >= 1; j --)
            f[j] = max(f[j] + a[i][j], f[j - 1] + a[i][j]);

    int res = INF;

    for (int i = 1; i <= n; i ++) res = max(res, f[i]);

    cout << res << endl;

    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

最长上升子序列

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

朴素做法

闫氏dp：

状态表示： f[i] , 1.集合：所有以第i个数字结尾的上升子序列

2.属性：max

状态计算：（注意，本题dp未用到 i-1 的递增公式，故 i 的下标从0开始）

分析集合：（ 0 | 1 | 2 | 3 |…| i-1）

在该集合中，题目要求数字大小逐渐上升，即 An-1< An 。

如果出现An-1>=An的情况，我们不会把它包含在集合中去，换言之，所求的都是满足题意的某个集合的最大值。

对于形如 AiAj 的上升子序列，可知f[j]的最长上升子序列，即f[i]的最长上升子序列+1。

故计算方程：f[ i ] = max( f[ j ] +1 ), j = 0,1,2,3… i-1 且 ( a[i]>a[j] ) 。

二分（数据加强版）

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

思路：

在朴素做法的基础上，我们需要追加一个集合,再次分析，来达到优化剪枝的效果。

分析：以 3 1 4 8 5 为例。如果一个子序列的长度为1，那该序列的末尾值可以取 1 ，也可以取 8。

如果要最长子序列，那末尾值就必须最小，也就是min(1,8) = 1 ，取1不取8。

为了实现该功能：

追加一个数组q[i] ,这个数组表示长度为i时，结尾最小的序列值为q[i]。所以该数组有效值的长度，就是最长上升子序列的长度。

遍历a数组里面的数，然后在q（这个数组的长度就是答案）这个数组里面查找是否存在一个大于且最靠近他的数，
若果不存在话，说明这个数是在q所有的数中是最大的
（这时下标也已经扫描到q数组的最右边，r这个下标已经定位到q的最右边，将其+1，更新q长度（即：更新答案）和新元素的值），
若存在（即：该点的值不是上升地），r+1也不会增加q的长度（因为不是上升的情况，所以这里答案不会更新），说明该点最长子序列一定是前面其中的某个答案，只需要将里面地最靠近的那个元素进行更新即可

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n;
int a[N] = {7,3,4,5,1,8,3};
int q[N];

int main()
{
    n=7;
    int len = 0;
    for (int i = 0; i < n; i ++ )
    {
        int l = 0, r = len;
        while (l < r)
        {
  //  q里有无大于当前a[i]:  存在原地，不存在的话更新 
  //                        不存在的话就是 r = 0
  //                         存在的话就是 r != 0 ，即大于1的线段，更新len 
  //                 （当然，如果有多个大于a[i]的数，则选择最靠近a[i]的。） 
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;// check()  
            else r = mid - 1;   
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];   
        printf("i = %d ,r = %d ,a[i]=%d , len = %d;  ",i,r,a[i],len);
        for(int i=0;i<n;i++) cout<<q[i]<<" ";
        cout<<endl;
    }    ///a[N] = {7,3,4,5,1,8,3};
	for(int i =0;i<n;i++) printf("q%d=%d\n",i,q[i]);
	cout<<endl; 
    printf("%d\n", len);

    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
38
39
40

注：此代码并非最终题解，因为保留了调试部分的输出语句和注释。

结果展示：

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

最长公共子序列

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

闫氏dp：

状态表示： f[i] [j] , 1.集合：字符串A的前i个字符，和字符串B的前j个字符的公共子序列

2.属性：max

状态计算：

以两个字符串的末位字符，即A[i] 和 B[j] 划分，有四种情况：

00 ：最长公共子序列的末尾字符，即不是A[i],也不是B[j] 。所以很自然，有 f(i,j) = f(i-1,j-1)

11 : 最长公共子序列的末尾字符,即是A[i],又是B[j]。所以必然有A[i] == B[j] 且f(i,j) = f(i-1,j-1)+1

01 : 末位不是A[i] ，但却是B[j]。经下面的分析，此种情况为 f(i,j) = f(i-1,j)

这里我们会想当然认为，f(i,j) = f(i-1,j)。但不是这样的。因为f(i-1,j) 同样包含了不选择B[j]的情况，这与我们的集合情况不符。但由于此题求的是最大值，根据前言原则2，所以重复不影响结果。

10 : 与01同理，重复无所谓，全覆盖就行。此种情况为 f(i,j) = f(i,j-1)

分析集合：（ 00|01|10|11）

集合00是被包含在01和10的集合中的。所以在状态转移方程中省去00。

状态转移方程：

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);

朴素做法

枚举i，j —— 状态转移

#include<iostream>
using namespace std ;
const int N = 1010;
int n,m;
char a[N],b[N];
int f[N][N];
int main(void)
{
    cin>>n>>m>>(a+1)>>(b+1); //下标从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);
        }
    }
    printf("%d",f[n][m]);
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

最短编辑距离

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

朴素做法

闫氏dp：

状态表示：f(i,j)

1.集合：将A[1~i] 操作后与B[1~j]相等的操作方式的集合

2.属性：min

状态计算：

( 删 | 增 | 改 )

删：删除之后匹配。删除多余的A[i]，即前面的最小值+1即现在的最小值。则有f(i,j ) = f(i-1,j)+1 ;
增：增加之后匹配。即A增加的值恰好是B[j] ,则有f(i,j) = f(i,j-1)+1 ;
改：更改（末尾值A[i])之后匹配。即要保证A[1~i-1] 和 B[1~j-1]是匹配的，再去改末位。

则有f(i,j) = f(i-1,j-1)+1 。

注意：这一步要判断。当A[1_i-1]与B[1j-1]匹配时，如果A[i]==B[j] 那就不需要再改末位，所以此时情况是f(i,j) = f(i-1,j-1)

代码：

#include<iostream>
using namespace std ;
const int N = 1010;
int f[N][N] ; //dp数组要建好
char A[N],B[N];

int main(void)
{
    int n,m;
    scanf("%d%s",&n,A+1);
    scanf("%d%s",&m,B+1);
    //dp前的初始化
    for(int i=0;i<=m;i++) f[0][i] = i; //当A的字符串是空，B的字符串长度为i，操作数即i（第i步增加B[i]），i<=m B的长度
    for(int j=0;j<=n;j++) f[j][0] = j; //当B的字符串是空，A的字符串长度为i，操作数即j (第j步删除A[i]) ，j<=n A的长度
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //增删
            f[i][j] = min(f[i-1][j]+1,f[i][j-1]+1);
            //改要判断
            if(A[i]==B[j]) f[i][j] = min(f[i][j],f[i-1][j-1]);
            else f[i][j] = min(f[i][j],f[i-1][j-1]+1);
        }
    }
    //输出结果：把A的前n个字母变成B的前m个字母
    cout<<f[n][m];
}
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

编辑距离

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

时间复杂度 ：n个字符串 , 每个字符串有 m次询问 n<=1000,m<=1000
字符串长度为10，比对时是n^2 ,即10^2 = 100

所以复杂度为： 1000 * 1000 * 100 = 10^8 , 有点紧。

给定 n个字符串，和当前字符串进行比较，求边界距离。

关键点在于求边界距离

边界距离的求法，可参考上一题“最短编辑距离“

朴素做法

#include<iostream>
#include<cstring>
using namespace std ;
const int N = 1010;
const int M = 15; //10
int f[N][N]; //dp数组
char str[N][M];//字符串数组，存储询问

//这里是最短编辑距离的算法。
int edit_distance(char a[],char b[]){
    
    int la = strlen(a + 1), lb = strlen(b + 1);

    for (int i = 0; i <= lb; i ++ ) f[0][i] = i;
    for (int i = 0; i <= la; i ++ ) f[i][0] = i;

    for (int i = 1; i <= la; i ++ )
        for (int j = 1; j <= lb; j ++ )
        {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }

    return f[la][lb];
}

int main(void)
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){
        scanf("%s",str[i]+1);
    }
    while(m--){  //开始询问：求给定 n 个字符串中，谁可以在上限操作次数内变成询问给出的字符串。
        char s[M];
        int limit; //上限次数
        scanf("%s%d",(s+1),&limit);
        
        int res = 0;
        for(int i=0;i<n;i++)  //遍历“给定字符串”
            if(edit_distance(str[i],s) <= limit ) //在边界范围内
                res++;
        
        cout<<res<<endl;
    }
    
    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
38
39
40
41
42
43
44
45
46
47
48

2.其他DP

区间dp

石子合并

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

数据范围： 1≤N≤300

闫氏dp分析：

状态表示：f(i,j)

集合：所有将[i,j]合并成一堆的集合

j-i+1的块，共 !(j-i) 种可能的情况
属性：min

状态计算： ( i |i+1|i+2| … | j-1 | j | )

f(i,j) 划分依据为左边的最后一堆的下标

每一类的最小值中，再取最小值即答案。

min = ( min (i,k) , min (k+1,j) )

分析第 k 类： f (i,j) = f(i,k) + f(k+1, j) + s[ j ] - s[i-1]

求权值时，用前缀和优化一下

#include<iostream>
using namespace std; 
const int N = 305;
int f[N][N];
int s[N];
int n;
int main(void)
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&s[i]);
    }
    for(int i=1;i<=n;i++)
    {
        s[i] += s[i-1];
    }
    	//区间dp 第一步：枚举区间长度  (区间长度为1不用枚举)
    for(int len = 2;len<=n;len++) 
        for(int l=1;l+len-1<=n;l++){ //最后只剩一堆，所以是<=n
            int r = l+len-1;
            f[l][r] = 1e8;              
            //截k点
            for(int k=l;k+1<=r;k++){  
           //对于[l, k] k可以取到 l 对于[k+1, r] ，因为k+1 <= r, 所以 k <= r - 1, 即 k < r
                f[l][r] = min(f[l][r],f[l][k]+f[k+1][r]+s[r]-s[l-1]);
            }
        }
    cout<<f[1][n];
}

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

f[l] [r]  = 1e8
1
这一步相当于初始化所有k的集合为最大值，这些集合还没有赋值。

答案则是在所有赋值后的k的集合中取最小值

复杂度： n * n *k , O(n^3) 。

n<=300 , 两百七十万的运算量。

外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

计数dp

整数划分

一个正整数 n可以表示成若干个正整数之和，形如：n=n1+n2+…+nk

其中 n1≥n2≥…≥nk, k≥1。

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

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

输入格式

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

输出格式

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

由于答案可能很大，输出结果请对 109+7109+7 取模。

数据范围

1≤n≤1000

输入样例:

5
1

输出样例：

7
1

dp写法：

状态表示：
- 集合：f( i , j ) : 所有总和是 i ，恰好表示成 j 个数的和的方案
- 属性：sum
状态计算：

f(i , j) ：根据最小值是1还是最小值大于1划分

>（最小值是1|最小值大于1）

最小值是1：数量等同于f[i-1,j-1]

也就是总和是 i-1,用 j-1 个数表示的方案

最小值大于1 ：数量等同于 f( i-j , j)

大于1的每个数，减去一个1，还是有j个数。

所以综上，sum = f(i , 1) + f(i , 2) + f(i , 3) +... f(i , i) .

const int N = 1010, mod = 1e9 + 7;

int n;
int f[N][N];

int main()
{
    cin >> 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

完全背包解法：

把这题抽象成，一个容量为 n 的背包，有 n 个物品：体积分别是1、2、 3 … n 。

状态表示：
- 集合：f( i , j ) : 所有从1到 i 中选，体积恰好是 j 的选法的数量
- 属性：sum
状态计算：
- f(i , j) ：根据最后一个物品选择了几个来定义划分区间。

（0|1|2|3|...|s）

f(i-1,j) | f(i-1,j-i)| f(i-1, j-2i)|...| f(i-1,j - s i)

故有：
f[i] [j]   =    f[i-1] [j] + f[i-1] [j-i] + f[i-1] [j-2i]+... f[i-1] [j-si]   //1
f[i] [j-i] =			     f[i-1] [j-i] + f[i-1] [j-2i]+... f[i-1] [j-si] //2
1
2
1-2 = f[i] [j] - f[i] [j-i] = f[ i-1 ] [j]

所以可得 f[i] [j] = f[i] [j-i]+ f[ i-1 ] [j]

同完全背包一样，压缩成一维：

f[j] = f [j-i]+ f [j]

#include<iostream>
using namespace std;

const int N = 1010;
int n;
int f[N][N]; // 使用前i个数恰好能组成数j的方案数
int mod = 1e9 + 7;

int main(){
    cin>>n;
    for(int i = 0; i <= n; i++)  f[i][0] = 1; // 使用前i个数组成0，每一个都有1种解法（都不选）
   //f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
        {
           // 注意，使用二维时需要一个优化，需要考虑当i比j小时的情况和i>=j的情况:
            //如果 i>j，就意味着一个也选不上，只能和 (i,i-1) 相同。
            f[i][j] = (f[i-1][j]) % mod; 
 
            if(j >= i) f[i][j] = (f[i][j] + f[i][j-i]) % mod; 
            // or  f[i][j] = (f[i][j-i] + f[i-1][j])%mod;
        }


    cout<<f[n][n];

    return 0;
}
/*
一维：
    cin>>n;
    for(int i=1;i<=n;i++) 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];
*/

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

数位统计dp

计数问题

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

例如，a=1024，b=1032，则 a 和 b 之间共有 99 个数如下：

1024 1025 1026 1027 1028 1029 1030 1031 1032
1

其中 0 出现 1010 次，1 出现 1010 次，2 出现 77 次，3 出现 33 次等等…

输入格式

输入包含多组测试数据。

每组测试数据占一行，包含两个整数 aa 和 bb。

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

输出格式

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

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

数据范围

0<a,b<100000000

核心思想：分情况讨论

核心函数：count(n,x) : 计算 1~n ，x出现的次数。

题解即 count(b,x) - count(a,x) 。

1~n , x =1

n = abcdefg

分别求出1在每一位上出现的次数

举例：

求1在第4位上出现的次数：

1<=xxx1yyy <= abcdefg

xxx = 000~abc-1 , yyy = 000~999 ：abc*1000
xxx=abc :
1. d<1 , abc1yyy > abc0efg : 0
2. d=1, yyy=000~efg ： efg+1
3. d>1, yyy=000~999 : 1000

复杂度：10 * 2 * 8 * 10 = 1600

10个数字，2次调用函数，8位， 10次函数内循环

边界问题：

枚举数字在最高位，情况一不存在

2.枚举数字 0 ，从001开始取到 abc 。因为不能有前导0。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 10;

int get(vector<int> num, int l, int r)  //数字 l~r 位的数字
{
    int res = 0; //注意：由于vector是逆序存数，所以这里也要逆序
    for (int i = l; i >= r; i -- ) res = res * 10 + num[i];
    return res;
}

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

int count(int n, int x) //1~n 中 x出现的次数
{
    if (!n) return 0; //1~0不计数

    vector<int> num;
    while (n) //反转数组，从右往左数
    {
        num.push_back(n % 10);
        n /= 10;
    }
    
    n = num.size();//记位数

    int res = 0;    //special 1 ↓
    for (int i = n - 1 - !x; i >= 0; i -- )  //从最左边开始遍历计数:求x在第i位的数量
    {  													//（针对所有范围内的抽象数)
        if (i < n - 1)
        {
            res += get(num, n - 1, i + 1) * power10(i);
            if (!x) res -= power10(i); //special 2
        }
		//这里上下是两种情况，上为x左位是 00...x~ab..x的情况，下为x..~x..ef的情况
        //逻辑上是两个并列循环，循环条件相同所以放在一个循环中。
        
        //1.num[i] < x:0 不计数，不考虑
        if (num[i] == x) res += get(num, i - 1, 0) + 1;//2.
        else if (num[i] > x) res += power10(i);
    }

    return res;
}

int main()
{
    int a, b;
    while (cin >> a >> 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;
}

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

count函数里，两个!x出现的位置即对于两个特殊情况的解。

1.枚举数字在最高位，情况一不存在。
for (int i = n - 1 - !x; i >= 0; i -- ) 
1
最左位不能是 0 (前置0)，如果 x 为 0，则遍历从 n-2开始；不为 0 则从 n-1开始。

2.x==0时，需要从001开始取到 abc
if (!x) res -= power10(i); 
1

注意：

count(b, i) - count(a - 1, i) << ' ';

res += get(num, n - 1, i + 1) * power10(i);

if (num[i] == x) res += get(num, i - 1, 0) + 1;
1
2
3
4
5

这三个边界是否要 +1、-1 很容易出差错。

树形dp

没有上司的舞会

Ural 大学有 NN 名职员，编号为 1∼N。

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

每个职员有一个快乐指数，用整数 HiHi 给出，其中 1≤i≤N。

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

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

输入格式

第一行一个整数 N。

接下来 N 行，第 i 行表示 ii 号职员的快乐指数 Hi。

接下来 N−1 行，每行输入一对整数 L,K，表示 K 是 L 的直接上司。（注意一下，后一个数是前一个数的父节点，不要搞反）。

输出格式

输出最大的快乐指数。

数据范围

1≤N≤6000，
−128≤Hi≤127

状态表示：f(u, 1/0)
- 集合：
  
  f( u , 0 ) : 从以u为根的子树当中选择，并且不选 u 的方案 ;
  
  f( u , 1 ) : 从以u为根的子树当中选择，并且选 u 的方案。
- 属性：max
状态计算：
- f( u , 0 ) : 不选 u，为了最大值，要选择子树中的最大值。(对每个子树，既可以选，也可以不选)
  
  f(u , 0) = ∑ max( f( si,1 ) ， f( si , 0) )
- f( u , 1 ) : 已经选u了，子树不能选了。
  
  f(u,1) = ∑ f(si,0)

时间复杂度：每个结点状态计算的是它的儿子，所以计算所有状态相当于遍历一遍，即 O(n)

此题画图更好理解。

类似状态机，但和状态机没什么关系。

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 6010;

int n;
int happy[N]; //开心值
int h[N],e[N],ne[N],idx;//邻接表
bool has_fa[N];//判断有无父节点，从而寻找根节点
int f[N][2]; //dp喽

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void dfs(int u)
{
    f[u][1] = happy[u];

    for (int i = h[u]; ~i; i = ne[i]) //~i <=> i!=-1
    {
        int j = e[i]; 
        dfs(j);

        f[u][1] += f[j][0];
        f[u][0] += max(f[j][0], f[j][1]);
    }
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d", &happy[i]);

    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        has_fa[a] = true;
    }

    int root = 1;
    while (has_fa[root]) root ++ ;

    dfs(root);

    printf("%d\n", max(f[root][0], f[root][1]));

    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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

记忆化搜索

滑雪

给定一个 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
1
2
3
4
5
6
7
8
9

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

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

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

输入格式

第一行包含两个整数 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
1
2
3
4
5
6

输出样例：

25
1

状态表示：f ( i , j ) 二维路径嘛。
- 集合：所有从( i,j )开始滑的路径中的最大值
- 属性：max
状态计算：

( ↑ | ↓ | ← | → )

时间复杂度：每个结点状态计算的是它的儿子，所以计算所有状态相当于遍历一遍，即 O(n)

存在一个最大值，如果所有结点的值都减去固定值，该值仍然作为最大值。

同理：如果你要求 (i , j) 点的最大值，假设向右遍历，则需要 (i+1, j ) 的最大值，也就是所谓的 :

f(i , j) = f( i+1 , j) +1。

但向右遍历只是一种情况。

考虑四种情况的式子为：f[i][j] = max(f[i][j],f[tx][ty]+1);

举个例子：

对于 25−24−23−…−3−2−1 ，这个路径的求取过程就是从右往左。

递归程序从 25 调用，一直到 1，再从右往左加和并回溯。

#include<iostream>
#include<memory.h>
using namespace std ;
const int N = 310;

int n,m;
int g[N][N];
int f[N][N];
int dir[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
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 tx = x + dir[i][0], ty = y + dir[i][1];
        if(tx>=1&&ty>=1&&tx<=n&&ty<=m&&g[tx][ty]<g[x][y])
        	v = max(v,dp(tx,ty)+1);
    }
    return v;
}
int main(void)
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>g[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)); //dp：所有以(i，j)为起点滑的路径中的最大值
        }
    cout<<res;
    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
38
39
40
41

状态压缩dp

蒙德里安的梦想

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

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

如下图所示：

输入格式

输入包含多组测试用例。

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

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

输出格式

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

数据范围

1≤N,M≤11

输入样例：

输出样例：

最短Hamilton路径

给定一张 n 个点的带权无向图，点从0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 n。

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

对于任意的 x,y,zx,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。

输出格式

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

数据范围

1≤n≤20
0≤a[i,j]≤107

输入样例：

输出样例：

18
1

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/357879

[做题]动态规划

文章目录

0.DP前言

1.线性DP

数字三角形

朴素做法

更优雅的写法

一维优化(朴素版本)

最长上升子序列

朴素做法

二分（数据加强版）

最长公共子序列

朴素做法

最短编辑距离

朴素做法

编辑距离

朴素做法

2.其他DP

区间dp

石子合并

计数dp

整数划分

dp写法：

完全背包解法：

数位统计dp

计数问题

树形dp

没有上司的舞会

记忆化搜索

滑雪

状态压缩dp

蒙德里安的梦想

最短Hamilton路径