中也者，天下之大本也。和也者，天下之达道也。

第五章动态规划

第五章动态规划

一、背包问题

总括：

背包类型	01背包	完全背包	多重背包	分组背包	混合背包
特点	对于物品而言只能选择1个或者0个两种情况	对于物品而言可以无限制选取,也可以不选	对于物品而言最多能够选择从s[i]个,同样也可不选	一些物品捆绑在一起,每一组物品中只能选择其中的一个物品	有些物品可以选择1个,有些物品可以选择无数个,有些物品只能选择s[i]个.即:01背包+完全背包+多重背包.
优化方式	暂无	暂无	二进制优化	暂无	其中多重背包部分参考多重背包优化

01背包

二维写法：

#include<iostream>
using namespace std;
const int N=1010;
int w[N],v[N];
int n,m,f[N][N];

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

一维写法：

#include <iostream>
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    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]); // 因为只用到第 i-1 行，则可以利用滚动数组，但是j如果从小到大枚举，max中的第二项就变成了f[i][j-v[i]]+w[i],我们需要的是第i-1行的结果，故而从大到小枚举可以解决这个问题

    cout << f[m] << endl;

    return 0;
}

完全背包

朴素写法：

// TLE
#include<iostream>
using namespace std;;
const int N=1010;
int v[N],w[N],n,m,f[N][N];

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

二维写法：

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w , …)
f[i , j-v] = max( f[i-1,j-v] , f[i-1,j-2v] +w , f[i-1,j-3v]+2w , …)
由上两式，可得出如下递推关系：
f[i] [j] =max(f[i-1] [j], f[i] [j-v[i]]+w[i])

#include<iostream>
using namespace std;;
const int N=1010;
int v[N],w[N],n,m,f[N][N];

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

一维写法：

#include<iostream>
using namespace std;;
const int N=1010;
int v[N],w[N],n,m,f[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];
    
    for(int i=1;i<=n;i++)
        for(int j=v[i];j<=m;j++)  // 注意此处不用像01背包的一维写法那样从大到小枚举，因为max中的第二项需要用到第i层的数据，也就是更新后的数据
            f[j]=max(f[j],f[j-v[i]]+w[i]);

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

多重背包

朴素写法：

数据范围在0～100时使用

#include<iostream>
using namespace std;
const int N=110;
int v[N],w[N],s[N];
int n,m,f[N][N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=0;k<=min(s[i],j/v[i]);k++){ // 所选个数既不能超过限制个数，也不能让总体积超过j
                f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
            }
        }
    }
    cout<<f[n][m]<<endl;
    return 0;
}

二进制优化写法：

数据范围>1000时使用

Q：为什么不能像完全背包一样去优化？

A：我们对比完全背包的和多重背包的优化推导

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v] = max( f[i-1,j-v] , f[i-1,j-2*v] +w , f[i-1,j-3*v]+2w , .....)

=> f[i] [j] =max(f[i-1] [j], f[i] [j-v[i]]+w[i])
f[i , j ] = max(f[i-1,j],f[i-1,j-v]+w , f[i-1,j-2*v]+2*w ,..... f[i-1,j-k*v]+k*w ,)
f[i , j-v] = max( f[i-1,j-v] , f[i-1,j-2*v] + w ,...... f[i-1,j-kv]+(k-1)w , f[i-1,j-(k+1)v] + kw)

完全背包是只要不超过总体积，可以一直选下去，多重背包则是，每一个物品都有数量限制，后面会多出一项，无法用取最大

核心思路：如果直接遍历转化为01背包问题，是每次都拿一个来问，取了好还是不取好。这样的时间复杂度是O(n^3),会TLE，运用二进制思想，比如：要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次，二进制优化则是：现在给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,…512分到10个箱子里，那么由于任何一个数字x ∈ [0,1023] 都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次。时间复杂度就从O(n^{3)下降到O(n}2 * logs) (s是每种物品限选数量)

#include<iostream>
using namespace std;
const int N = 12010, M = 2010;

int n, m;
int v[N], w[N]; //逐一枚举最大是N*logS
int f[M]; // 体积<M

int main()
{
    cin >> n >> m;
    int cnt = 0; //分组的组别
    for(int i = 1;i <= n;i ++)
    {
        int a,b,s;
        cin >> a >> b >> s;
        int k = 1; // 组别里面的个数
        while(k<=s)
        {
            cnt ++ ; //组别先增加
            v[cnt] = a * k ; //整体体积
            w[cnt] = b * k; // 整体价值
            s -= k; // s要减小
            k *= 2; // 组别里的个数增加
        }
        //剩余的一组
        if(s>0)
        {
            cnt ++ ;
            v[cnt] = a*s; 
            w[cnt] = b*s;
        }
    }

    n = cnt ; //枚举次数正式由个数变成组别数

    //对新划分的组做一遍01背包
    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;
}

分组背包

核心思路：相对于01背包，集合f [i,j]表示为从前 i 组物品中选，总体积不超过 j 的所有选法

#include<iostream>
using namespace std;
const int N=110;
int w[N][N],v[N][N];
int s[N],f[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        for(int j=0;j<s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
    
    for(int i=1;i<=n;i++)
        for(int j=m;j>=1;j--)
            for(int k=0;k<=s[i];k++)
                if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
    
    cout<<f[m]<<endl;
    return 0;
}

二、线性DP

最长上升子序列 I

给定一个长度为 N 的数列，求数值严格单调递增的子序列的长度最长是多少。

输入格式

第一行包含整数 N。

第二行包含 N 个整数，表示完整序列。

输出格式

输出一个整数，表示最大长度。

数据范围

1 ≤ N ≤1000，
−10^9 ≤ 数列中的数 ≤ 10^9

输入样例：

1 2	7 3 1 2 1 8 5 6

输出样例：

// 时间复杂度：O(n^2)
#include<iostream>
using namespace std;
const int N=1010;
int f[N],a[N];
int n;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=1;
    }
    
    for(int j=1;j<=n;j++){
        for(int i=1;i<j;i++){
            if(a[i]<a[j]) f[j]=max(f[j],f[i]+1);
        }
    }
    
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    cout<<res<<endl;
    return 0;
}

最长上升子序列 II

当数据范围 1 ≤ N ≤100000时，需要优化

// 时间复杂度：O(nlogn)
#include<iostream>
using namespace std;
const int N=100010;
int a[N];
int q[N];  // q[i]表示长度为 i 的上升子序列的最后一个元素的值，q是严格单调递增的
int n;

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    int len=0;
    for(int i=0;i<n;i++){
        int l=0,r=len;
        while(l<r){   // 二分找到小于当前元素的最大值，
            int mid=(l+r+1)>>1;
            if(q[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        q[r+1]=a[i];
        len=max(len,r+1);
    }
    cout<<len<<endl;
    return 0;
}

最长公共子序列

给定两个长度分别为 N 和 M 的字符串 A 和 B，求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少。

输入格式

第一行包含两个整数 N 和 M。

第二行包含一个长度为 N 的字符串，表示字符串 A。

第三行包含一个长度为 M 的字符串，表示字符串 B。

字符串均由小写字母构成。

输出格式

输出一个整数，表示最大长度。

数据范围

1≤N,M≤1000

输入样例：

1
2
3

4 5
acbd
abedc

输出样例：

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N],n,m;
char a[N],b[N];

int main(){
    cin>>n>>m;
    cin>>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;
}

最短编辑距离

给定两个字符串 A 和 B，现在要将 A 经过若干操作变为 B，可进行的操作有：

删除–将字符串 A 中的某个字符删除。
插入–在字符串 A 的某个位置插入某个字符。
替换–将字符串 A 中的某个字符替换为另一个字符。

现在请你求出，将 A 变为 B 至少需要进行多少次操作。

输入格式

第一行包含整数 n，表示字符串 A 的长度。

第二行包含一个长度为 n 的字符串 A。

第三行包含整数 m，表示字符串 B 的长度。

第四行包含一个长度为 m 的字符串 B。

字符串中均只包含大小写字母。

输出格式

输出一个整数，表示最少操作次数。

数据范围

1≤n,m≤1000

输入样例：

10 
AGTCTGACGC
11
AGTAAGTAGGC

输出样例：

#include<iostream>
using namespace std;
const int N=1010;
int f[N][N];
char a[N],b[N];

int main(){
    int n,m;
    cin>>n>>a+1>>m>>b+1;
    for(int i=1;i<=n;i++) f[i][0]=i;  // B为空，需要删除i次
    for(int i=1;i<=m;i++) f[0][i]=i;  // A为空，需要插入i次
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i-1][j],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);
        }
    }
    
    cout<<f[n][m]<<endl;
    return 0;
}

三、区间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

输入样例：

1
2

4
1 3 5 2

输出样例：

#include<iostream>
using namespace std;
const int N=310;
int f[N][N],s[N];
int n;

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) {  // 前缀和
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int len=2;len<=n;len++){  // 首先要枚举区间，len=1没有意义
        for(int i=1;i+len-1<=n;i++){
            int l=i,r=i+len-1;
            f[l][r]=1e8;
            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;
}

四、计数类DP

整数划分

一个正整数 nn 可以表示成若干个正整数之和，形如：n=n1+n2+…+nk，其中 n1≥n2≥…≥nk,k≥1。

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

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

输入格式

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

输出格式

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

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

数据范围

1≤n≤1000

输入样例:

输出样例：

算法一：转化为完全背包问题

#include<iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],n;
int main(){
    cin>>n;
    f[0]=1;  // 背包问题计算方案数一般初始化为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;
}

算法二：

#include<iostream>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N][N],n;
int main(){
    cin>>n;
    f[0][0]=1;
    for(int i=1;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;
}

五、数位统计DP

计数问题

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

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

1	1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 10 次，1 出现 10 次，2 出现 7 次，3 出现 3 次等等…

输入格式

输入包含多组测试数据。

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

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

输出格式

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

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

数据范围

0<a,b<100000000

输入样例：

输出样例：

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

#include<iostream>
#include<cmath>
using namespace std;

int num(int x){ // 计算整数x有多少位
    int res=0;
    while(x){
        x/=10;
        res++;
    }
    return res;
}

int count(int n,int i){     // 计算从1到n的整数中数字i出现多少次 
    int res=0,d=num(n);     // d表示整数n的位数
    for(int j=1;j<=d;j++){  //从右往左枚举，数字i在第j位出现的次数，然后累加
        //l表示第j位数字左边的数，r表示第j位数字右边的数，dj表示第j位上的数字
        int p=pow(10,j-1),l=n/p/10,r=n%p,dj=n/p%10;

        // 以下分了四种情况
        if(l){                    // 当j不是最高位时，即l!=0
            if(i) res+=l*p;       // 统计的数字i不为0，则左边的数的范围为0～l-1，右边的范围为0～p-1
            else res+=(l-1)*p;    // 统计数字为0，与上面相比，左边的数的范围为1～l-1，不能从0开始，否则第j位失去意义
            // 不管i是否为零，当第j位数字左边的数=l时，右边的数照加不误
            if(dj>i) res+=p;      // 右边的数的范围为0～p-1
            if(dj==i) res+=r+1;   // 右边的数的范围为0～r
        }
        else{                     // 当j是最高位时，即l=0
            if(i) {
                if(dj>i) res+=p;
                if(dj==i) res+=r+1;
            }                     // 0不可能处于最高位，不考虑
        }
    }
    return res;
}

int main(){
    int a,b;
    while(cin>>a>>b,a || b){
        if(a>b) swap(a,b);           // 小的在前，大的在后，方便后续计算
        for(int i=0;i<10;i++){
            cout<<count(b,i)-count(a-1,i)<<' ';  //可以与前缀和类比
        }
        cout<<endl;
    }

    return 0;
}

六、状态压缩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

输入样例：

输出样例：

#include <bits/stdc++.h>
using namespace std;
const int N = 12, M = 1<< N;  

long long f[N][M] ;// 第一维表示列， 第二维表示所有可能的状态
bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。

//vector<int > state[M];  //二维数组记录合法的状态
vector<vector<int>> state(M);  //两种写法等价:二维数组
int m, n;

int main() {

    while (cin >> n >> m, n || m) { //读入n和m，并且不是两个0即合法输入就继续读入

        //第一部分：预处理1
        //对于每种状态，先预处理每列不能有奇数个连续的0

        for(int i = 0; i < (1 << n); i ++) {

            int cnt = 0 ;//记录连续的0的个数

            bool isValid = true; // 某种状态没有奇数个连续的0则标记为true

            for(int j = 0; j < n; j ++) { //遍历这一列，从上到下

                 if ( (i >> j) & 1) {  
                     //i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位； 
                     // &1为判断该位是否为1，如果为1进入if
                    if (cnt & 1) { 
                    //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                        isValid =false; break;
                    } 

                    cnt = 0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                    //其实清不清零没有影响
                 }
                 else cnt ++; //否则的话该位还是0，则统计连续0的计数器++。
            }
            if (cnt & 1)  isValid = false; //最下面的那一段判断一下连续的0的个数

            st[i]  = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
        }

        //第二部分：预处理2
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
        //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突

        for (int j = 0; j < (1 << n); j ++) { //对于第i列的所有状态
            state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。

            for (int k = 0; k < (1 << n); k ++) { //对于第i-1列所有状态
                if ((j & k ) == 0 && st[ j | k]) 
                // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
                //解释一下st[j | k] 
                //已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
                //我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，
                //还要考虑自己这一列（i-1列）横插到第i列的
                //比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
                //那么合在第i-1列，到底有多少个1呢？
                //自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101
                //这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的

                    state[j].push_back(k);  
                    //二维数组state[j]表示第j行， 
                    //j表示 第i列“真正”可行的状态，
                    //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
                    //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }

        }

        //第三部分：dp开始

        memset(f, 0, sizeof f);  
        //全部初始化为0，因为是连续读入，这里是一个清空操作。
        //类似上面的state[j].clear()

        f[0][0] = 1 ;// 这里需要回忆状态表示的定义
        //按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。
        //其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for (int i = 1; i <= m; i ++) { //遍历每一列:第i列合法范围是(0~m-1列)
            for (int j = 0; j < (1<<n); j ++) {  //遍历当前列（第i列）所有状态j
                for (auto k : state[j])    // 遍历第i-1列的状态k，如果“真正”可行，就转移
                    f[i][j] += f[i-1][k];    // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
            }
        }

        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数

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

    }
}

最短Hamilton路径

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

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

输入格式

第一行输入整数 n。

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

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

输出格式

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

数据范围

1 ≤ n ≤ 20
0 ≤ a[i,j] ≤ 10^7

输入样例：

输出样例：

#include<iostream>
#include<cstring>
using namespace std;

const int N=20,M=1<<N;
int f[M][N],w[N][N];

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>w[i][j];
            
    memset(f,0x3f,sizeof f);
    f[1][0]=0; // 初始化0号点已经过，距离为0
    for(int i=0;i<1<<n;i++){  // 枚举每个点是否经过得到一个状态
        for(int j=1;j<n;j++){
            if(i>>j&1){   // 枚举经过的每个点
                for(int k=0;k<n;k++){
                    if(i>>k&1) f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]);
                }
            }
        }
    }
    
    cout<<f[(1<<n)-1][n-1]<<endl;
    return 0;
}

七、树形DP

没有上司的舞会

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

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

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

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

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

输入格式

第一行一个整数 N。

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

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

输出格式

输出最大的快乐指数。

数据范围

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

输入样例：

输出样例：

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6010;
int h[N],e[N],ne[N],idx;
int f[N][2],n,happy[N];
int st[N]; // 判断每个节点是否有父节点

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!=-1;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[u][0]+=max(f[j][1],f[j][0]);
        f[u][1]+=f[j][0];
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>happy[i];
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++) {
        int a,b;
        cin>>a>>b;
        add(b,a);
        st[a]=true;
    }
    int root=1;
    for(int i=1;i<=n;i++) {
        if(!st[i]) {
            root=i;
            break;
        }
    }
    
    dfs(root);
    cout<<max(f[root][0],f[root][1])<<endl;
    return 0;
}

八、记忆化搜索

滑雪

给定一个 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 ≤ 矩阵中整数 ≤ 100000

输入样例：

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

输出样例：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=310;
int h[N][N],f[N][N];
int n,m;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};

int dp(int x,int y){
    if(f[x][y]!=-1) return f[x][y]; // 记忆化搜索的体现
    f[x][y]=1;
    for(int i=0;i<4;i++){
        int a=x+dx[i],b=y+dy[i];
        if(a<0 || a>=n || b<0 || b>=m || h[a][b]>=h[x][y]) continue;
        f[x][y]=max(f[x][y],dp(a,b)+1);
    }
    return f[x][y];
}

int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin>>h[i][j];
        
    memset(f,-1,sizeof f);
    int res=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            res=max(res,dp(i,j));
        }
    }
    cout<<res<<endl;
    return 0;
}

第五章 动态规划

一、背包问题

总括：

01背包

二维写法：

一维写法：

完全背包

朴素写法：

二维写法：

一维写法：

多重背包

朴素写法：

二进制优化写法：

分组背包

二、线性DP

最长上升子序列 I

输入格式

输出格式

数据范围

输入样例：

输出样例：

最长上升子序列 II

最长公共子序列

输入格式

输出格式

数据范围

输入样例：

输出样例：

最短编辑距离

输入格式

输出格式

数据范围

输入样例：

输出样例：

三、区间DP

石子合并

输入格式

输出格式

数据范围

输入样例：

输出样例：

四、计数类DP

整数划分

输入格式

输出格式

数据范围

输入样例:

输出样例：

算法一：转化为完全背包问题

五、数位统计DP

计数问题

输入格式

输出格式

数据范围

输入样例：

输出样例：

六、状态压缩DP

蒙德里安的梦想

输入格式

输出格式

数据范围

输入样例：

输出样例：

最短Hamilton路径

输入格式

输出格式

数据范围

输入样例：

输出样例：

七、树形DP

没有上司的舞会

输入格式

输出格式

数据范围

输入样例：

输出样例：

八、记忆化搜索

滑雪

输入格式

输出格式

第五章动态规划