背包九讲

01背包问题

有N件物品和一个容量是V的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

有限集合的最大值问题，用闫氏DP分析法：

DP问题：

  1. 状态表示f(i,j):
    • 集合：所有只考虑前i个物品，且总体积不超过j的选法的集合
    • 属性：max（价值最大）
  2. 状态计算：（不重不漏的分为这两种）
    • 所有不选择第i个物品的方案（1~i-1中选，且总体积≤j）f(i-1,j)
    • 所有选择第i个物品的方案（1~i-1中选，且总体积≤j-v[i]）f(i-1,j-v[i])+w[i]
    • f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[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
30
31
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    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++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

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

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>v[i]>>w[i];
    for(int i=0;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;
}

完全背包问题

有N件物品和一个容量是V的背包。每件物品能使用无限次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

DP问题：

  1. 状态表示f(i,j):

    • 集合：所有只考虑前i个物品，且总体积不超过j的选法的集合
    • 属性：max（价值最大）

  2. 状态计算：（不重不漏的分为这两种）

    • 所有不选择第i个物品的方案（1~i-1中选，且总体积≤j）f(i-1,j)
    • 所有选择1个第i个物品的方案（1~i-1中选，且总体积≤j-v[i]）f(i-1,j-v[i])+w[i]
    • 所有选择2个第i个物品的方案
    • …
    • 所有选择k个第i个物品的方案 （1~i-1中选，且总体积≤j-k*v[i]）f(i-1,j-v[i])+w[i]*k

    曲线救国：

    • f(i,j)=max(f(i-1,j),f(i-1,j-k*v[i])+k*w[i]);
    • f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],f(i-1,j-3*v[i])+3*w[i]….);
    • f(i,j-v)=max( f(i-1,j-v[i]), f(i-1,j-2*v[i])+w[i], f(i-1,j-3*v[i])+2*w[i]….);
    • f(i,j)=max(f(i-1,j),f(i,j-v)+w[i])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int n,m;
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-k*v[i]]+w[i]*k);
        }//f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i])
    }
    cout<<f[n][m]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],f[N];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++) cin>>v[i]>>w[i];
    for(int i=0;i<=n;i++){//本层i，从小到大枚举体积
        for(int j=v[i];j<=m;j++) f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[m]<<endl;
    return 0;
}

多重背包问题

有N件物品和一个容量是V的背包。每件物品能使用si次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

DP问题：

  1. 状态表示f(i,j):

    • 集合：所有只考虑前i个物品，且总体积不超过j的选法的集合
    • 属性：max（价值最大）

  2. 状态计算：（不重不漏的分为这几种）

    • 所有不选择第i个物品的方案（1~i-1中选，且总体积≤j）f(i-1,j)
    • 所有选择1个第i个物品的方案（1~i-1中选，且总体积≤j-v[i]）f(i-1,j-v[i])+w[i]
    • 所有选择2个第i个物品的方案
    • …
    • 所有选择si个第i个物品的方案 （1~i-1中选，且总体积≤j-si*v[i]）f(i-1,j-v[i])+w[i]*si
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],f[N][N];
int n,m;
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=0;j<=m;j++){
        	for(int k=0;k<=s[i]&&k*v[i]<=j;k++) f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+w[i]*k);
        }//f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i])
    }
    cout<<f[n][m]<<endl;
    return 0;
}

曲线救国：

  • f(i,j)=max(f(i-1,j),f(i-1,j-k*v[i])+k*w[i]);(k=0,1,2…si)
  • f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i]…f(i-1,j-si*v[i])+si*w[i]);
  • f(i,j-v)=max( f(i-1,j-v[i]), f(i-1,j-2*v[i])+w[i], f(i-1,j-si*v[i])+(si-1)*w[i]+f(i-1,j-(si+1)*v[i])+si*w[i]);
  • f(i,j)=max(f(i-1,j),f(i,j-v)+w[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
30
#include<iostream>//二进制的优化方式，打包成1/2/4/8..个第i个物品，每一包只能用一次，看成01背包问题
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=2010;
int f[N];
int n,m,v,w,s;
struct Good{
    int v,w;
};
int main(){
    cin>>n>>m;
    vector<Good> goods;
    for(int i=0;i<n;i++){
        cin>>v>>w>>s;
        for(int k=1;k<=s;k=k*2){
            s=s-k;
            goods.push_back({k*v,k*w});//打包的体积、价值
        }
        if(s>0) goods.push_back({s*v,s*w});//补上最后的
    }
    for(auto good:goods){
        for(int j=m;j>=good.v;j--){
        f[j]=max(f[j],f[j-good.v]+good.w);
    }
    }
    cout<<f[m];
    return 0;
}

分组背包问题

有N件物品和一个容量是V的背包。每件物品能使用si次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

DP问题：

  1. 状态表示f(i,j):

    • 集合：所有只考虑前i组物品，且总体积不超过j的选法的集合
    • 属性：max（价值最大）

  2. 状态计算：（不重不漏的分为这几种）

    • 所有不选择第i组物品的方案（1~i-1组中选，且总体积≤j）f(i-1,j)
    • 所有选择第i组第1个物品的方案（1~i-1组中选，且总体积≤j-v[i]）f(i-1,j-v[i,1])+w[i,1]
    • 所有选择第i组第2个物品的方案
    • …
    • h所有选择第i组第k个物品的方案 （1~i-1组中选，且总体积≤j-si*v[i]）f(i-1,j-v[i,k])+w[i,k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s;
const int N=110;
int v[N],w[N],f[N];
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>s;//每组个数
        for(int j=0;j<s;j++) cin>>v[j]>>w[j];
        for(int j=m;j>=0;j--){
            for(int k=0;k<s;k++){
                if(j>=v[k]) f[j]=max(f[j],f[j-v[k]]+w[k]);
            }
        }
    }
    cout<<f[m];
    return 0;
}

线性DP

数字三角形

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

1
2
3
4
5
1        7（1）
2      3   8（2）
3     8   1   0（3）
4   2   7   4   4（4）
5  4   5   2   6   5（5）

动态规划：

  1. 状态表示f(i,j):

    • 集合：所有从起点走到（i，j)的路径
    • 属性：max（集合中所有路径上数字之和的最大值）

  2. 状态计算：（不重不漏的分为这几种）

    • 从左上方来的
    • 从右上边来的

    曲线救国：

    • f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
using namespace std;
const int N=510,INF=1e9;
int a[N][N],n;//存储每一个点
int f[N][N];//存储状态
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;i++){
        for(int j=0;j<=i+1;j++) 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-1]+a[i][j],f[i-1][j]+a[i][j]);
    }
    int res=-INF;
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);//遍历最后一行
    cout<<res;
    return 0;
}

最长上升子序列

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

动态规划：

  1. 状态表示f(i):

    • 集合：所有以第i个数结尾的上升子序列的集合
    • 属性：max（集合中每一个上升子序列的长度的最大值）

  2. 状态计算：（不重不漏的分为这几种）

    • 序列长度为1
    • 倒数第二个数为a1
    • 倒数第二个数为a2
    • …
    • 倒数第二个数为ai-1
    • 每一类不一定都存在

    曲线救国：

    • f[i]=max(f[j]+1);j=0,1,2,…,i-1

时间复杂度：状态数量*每一个计算需要的时间（n*n)

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=1010;
int f[N],a[N];
int n;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++){
        f[i]=1;//只有a[i]一个数
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i]) f[i]=max(f[j]+1,f[i]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    printf("%d",res);
    return 0;
}

最长上升子序列-数据范围->100000

3 1 2 1 8 5 6

3能接的，1也能接，因此3没有必要了

因此，长度相同的，只需要存储结尾最小的就可以了

所有长度下，最长上升子序列的结尾值

可证明：结尾越长，数值单调递增。

证明：设5、6长度的结尾相等，则6的前一个数比5结尾的数小，矛盾了

因此，只需要把ai接到小于他的最大的数后面就行了（用二分法找到这个数)

时间复杂度：O(logn)

每次求的时候的冗余：

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
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N],f[N];//所有不同长度子序列结尾的最小值
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    f[0]=-2e9;//边界
    int len=0;//最大长度为0（q的元素个数）
    for(int i=0;i<n;i++){//找到小于a[i]的最大数
        int l=0,r=len;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(f[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        f[r+1]=a[i];
        len=max(len,r+1);
    }
    printf("%d\n",len);
    return 0;
}

最长公共子序列

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

动态规划：

  1. 状态表示f(i,j):

    • 集合：所有在第一个序列的前i个字母和第二个序列的前j个字母中出现的子序列
    • 属性：max（所有公共子序列的长度的最大值）

  2. 状态计算：（不重不漏的分为这几种）

    • 00：a[i]b[j]都不在子序列中（包含于后面两种情况）
    • 01：b[j]在子序列中(包含于f[i-1,j])
    • 10：a[i]在子序列中(包含于f[i,j-1])
    • 11：a[i]b[j]都在子序列中

    曲线救国：

    • f[i，j]=max(f[i-1][j-1],f[i-1,j],f[i,j-1],f[i-1][j-1]+1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;
char a[N],b[N];
int n,m,f[N][N];
int main(){
    cin>>n>>m;
    scanf("%s%s",a+1,b+1);//用到了i-1,j-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]);
    return 0;
}

最短编辑距离

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

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

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

==动态规划==：

  1. 状态表示f(i,j):

    • 集合：所有将a[1~i]变成b[1~j]的操作方式
    • 属性：min（所有操作次数的最小值）

  2. 状态计算：（不重不漏的分为这几种）

    • 删A[i]，f[i-1,j]+1
    • 增A[i]（和b[j]相同），a[i]和b[j-1]匹配，f[i,j-1]+1
    • 改a[i-1]和b[j-1]匹配，f[i-1,j-1]+1

    曲线救国：

    • f[i，j]=min(f[i-1,j]+1，f[i,j-1]+1，f[i-1,j-1]+1)
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>
#include<cstring>
using namespace std;
const int N=1010;
int n,m,f[N][N];
char a[N],b[N];
int main(){
    scanf("%d%s",&n,1+a);//状态转移涉及i-1，下边从1开始
    scanf("%d%s",&m,1+b);
    for(int i=0;i<=m;i++) f[0][i]=i;//开始a没有，要添加i个
    for(int i=0;i<=n;i++) f[i][0]=i;//开始b没有，要删除i个
    for(int i=1;i<=n;i++){//DP
        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]=f[i-1][j-1];
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

区间DP

设有 NN 堆石子排成一排，其编号为 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。

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

==动态规划==：

  1. 状态表示f(i,j):

    • 集合：所有将第i堆石子到第j堆石子合并成一堆石子的合并方式
    • 属性：min（）

  2. 状态计算：（不重不漏的分为这几种）

    • 最后一次分类时候左边1个
    • 最后一次分类时候左边2个
    • ….
    • 最后一次分类时候左边k-1个

    曲线救国：

    • f[i，j]=min(f[i,k]+f[k+1,j]+st[j]-s[i-1]) k=i,…,j-1
    • 时间按复杂度O(n^3^)
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
#include<iostream>
#include<algorithm>
using namespace std;
const int N=310;
int n,m,f[N][N],s[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++){
        
        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]);
            }
        }
    }
    printf("%d",f[1][n]);
    return 0;
}

整数划分

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

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

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

看成背包容量为n，物品为1~n,无限个，完全背包问题

==动态规划==：

  1. 状态表示f(i,j):

    • 集合：所有1~i中选，体积恰好是j的选法的数量
    • 属性：数量

  2. 状态计算：（不重不漏的分为这几种）

    • 第i个物品选择了0个 f(i-1,j)
    • 第i个物品选择了1个 f(i-1,j-i)
    • 第i个物品选择了2个 f(i-1,j-2*i)
    • ….
    • 第i个物品选择了s个 f(i-1,j-i*s)

    曲线救国：

    • f[i][j]=f[i-1][j]+f[i-1][j-i]+…+f[i-1][j-i*s]
    • f[i][j-1]= f[i-1][j-1]+f[i-1][j-i]+…+f[i-1][j-i*s]
    • f[i][j]=f[i-1][j]+f[i][j-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010,mod=1e9+7;
int f[N],s[N];
int main(){
    int n;
    cin>>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;
        }
    }
    printf("%d",f[n]);
    return 0;
}

计数问题

给定两个整数 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 次等等…

设n=abcdefg

  1. 001~abc x 000~999 abc*1000
  2. abc x
    • 2.1 d<x 0
    • 2.2 d=x 000~efg efg+1
    • 2.3 d>x 000~999 1000
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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
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){//求10的i次方
    int res=1;
    for(int i=0;i<x;i++)
    {
        res=res*10;
    }
    return res;
}
int count(int n,int x){//从1~n中统计x出现的次数
    if(n==0) return 0;
    vector<int> num;
    while(n){//抠出来n的每一位
        num.push_back(n%10);
        n=n/10;
    }
    n=num.size();//n为位数
    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+=power10(i);
        }
        else if(num[i]==x){
            res+=get(num,i-1,0)+1;
        }
    }
    return res;
}
int main(){
    int n,a,b;
    while(cin>>a>>b&&a||b!=0){
        if(a>b) swap(a,b);
        for(int i=0;i<10;i++){
            printf("%d ",count(b,i)-count(a-1,i));
        }
        printf("\n");
    }
    return 0;
}

蒙德里安的梦想

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

当我们把横向放完时，竖向也确定了

f[i,j]：摆放第i列，其中第j行是从上一列伸出来的；j=0~31

如图，f[2]=(10010)2

判断能否转移过来：如f[3]=(00001)2:

  • (j&k)=0
  • 所有连续的空白格子是偶数，j|k不存在连续奇数个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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<bits/stdc++.h>
using namespace std;
const int N=12,M=1<<N;
long long f[N][M];
bool st[M];
int main(){
    int n,m;
    while(cin>>n>>m&&(n||m)){
        for(int i=0;i<1<<n;i++){//预处理每种状态连续0的个数
            int cnt=0;//连续0的个数
            st[i]=true;
            for(int j=0;j<n;j++){
                if(i>>j&1) {
                    if(cnt&1) st[i]=false;//奇数0
                }
                    else cnt++;
            }
            if(cnt&1) st[i]=false;//最后一段0的个数
        }
        memset(f,0,sizeof f);
    f[0][0]=1;//最一开始的时候第0列什么也没有放
    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])){//如果jk没有冲突，j|k不存在连续奇数个0
                    f[i][j]+=f[i-1][k];
                }
            }
        }
    }
    printf("%lld\n",f[m][0]);//枚举到第0列的时候，应该都是0
    }
    
    return 0;
}

没有上司的舞会（树形DP）

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

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

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

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

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

==动态规划==：

  1. 状态表示f[u][0],[u][1]:

    • 集合：
      • f[u][0]:所有从以u为跟的子树中选择,并且不选择u这个点的方案
      • f[u][1]:所有从以u为跟的子树中选择,并且选择u这个点的方案
    • 属性：Max

  2. 状态计算：（不重不漏的分为这几种）

    • f[s1][0]
    • f[s1][1]
    • f[s2][0]
    • ….
    • f[s1][0]

    曲线救国：

    • f[u][0]=Σmax(f[si][0],f[si][1])
    • f[u][1]=Σmax(f[si][0],)

    时间复杂度：O(n-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
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=6010;
int e[N],h[N],n,ne[N],idx,happy[N];//树是一种特殊的图，使用邻接表存储
bool has_father[N];
int f[N][2];
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int x){
    f[x][1]=happy[x];
    for(int i=h[x];i!=-1;i=ne[i]){
        int j=e[i];
        dfs(j);
        f[x][1]+=f[j][0];
        f[x][0]+=max(f[j][0],f[j][1]);
    }
    
}
int main(){
    cin>>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);
        has_father[a]=true;
        add(b,a);
    }
    int root=1;
    while(has_father[root]) root++;
    dfs(root);
    //cout<<root<<endl;
    cout<<max(f[root][1],f[root][0]);
    return 0;
}z

滑雪

给定一个 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，沿途共经过 25 个区域。

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

==动态规划==：

  1. 状态表示f[i][j]:

    • 集合：f[i][j]:所有从i,j开始滑的路径
    • 属性：Max

  2. 状态计算：（不重不漏的分为这几种）

    • f[i][j]第一步是向上滑f[i-1][j]+1
    • f[i][j]第一步是向下滑f[i+1][j]+1
    • f[i][j]第一步是向左滑f[i][j-1]+1
    • f[i][j]第一步是向右滑f[i][j+1]+1

    曲线救国：

    • f[i][j]=Σmax(f[i-1][j]+1,f[i+1][j]+1,f[i][j-1]+1,f[i][j+1]+1)
    • 路线一定不存在环

    时间复杂度：O(n-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
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=310;
int h[N][N],f[N][N],n,m;//每个点的高度
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};//偏移量
int dp(int x,int y){
    int &v=f[x][y];//所有的x等价于f[x][y]
    if(v!=-1) return f[x][y];
    v=1;
    for(int i=0;i<4;i++){
        int aa=x+dx[i],bb=y+dy[i];
        if(aa>=1&&aa<=n&&bb>=1&&bb<=m&&h[aa][bb]<h[x][y]){
            v=max(v,dp(aa,bb)+1);
        }
    }
    return v;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>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));//i,j的状态
        }
    }
    cout<<res;
    return 0;
}