区间dp

石子合并

1680493305778

数据范围 ： 1≤N≤300

闫氏dp分析：

状态表示：f(i,j)

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

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

  2. 属性 ：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]

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

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<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
f[l] [r]  = 1e8

这一步相当于初始化所有k的集合为最大值，这些集合还没有赋值。

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

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

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

1685010071521

计数dp

整数划分

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

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

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

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

输入格式

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

输出格式

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

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

数据范围

1≤n≤1000

输入样例:

1
5

输出样例：

1
7

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

完全背包解法：

把这题抽象成，一个容量为 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)

故有：

1
2
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 = 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] 

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>
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];
*/

数位统计dp

计数问题

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

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

1
1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 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 = 000abc-1 , yyy = 000999 ：==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。

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
#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;
}

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

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

1
for (int i = n - 1 - !x; i >= 0; i -- )

最左位不能是 0 (前置0)，如果 x 为 0，则遍历从 n-2开始；不为 0 则从 n-1开始。

2.x==0时 ，需要从001开始取到 abc 

1
if (!x) res -= power10(i);

注意：

1
2
3
4
5
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、-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)

此题画图更好理解。

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

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
#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;
}

记忆化搜索

滑雪

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

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

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

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

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

1
2
3
4
5
6
7
8
9
 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，沿途共经过 2525 个区域。

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

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

1
2
3
4
5
6
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
25

  • 状态表示：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，再从右往左 加和 并回溯。

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
#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;
}

状态压缩dp

蒙德里安的梦想

求把 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
3
4
5
6
7
8
9
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
2
3
4
5
6
7
8
1
0
1
2
3
5
144
51205

最短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

输入样例：

1
2
3
4
5
6
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

输出样例：

1
18

快来参与讨论吧~