普通dp

普通dp是指一些很浅显的、可以由无后效性和最优子结构得出答案的题目

非常基础的题目：

P1216 数字三角形

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1001][1001];
int main(){
    cin>>n;
    int maxNum=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            int now;
            cin>>now;
            int j1=(j-1)>=1?j-1:1,j2=(j<=i-1)?j:i-1;
            dp[i][j]=now+max(dp[i-1][j1],dp[i-1][j2]);
            if(maxNum<dp[i][j])
                maxNum=dp[i][j];
        }
    }
    cout<<maxNum;
    return 0;
}

记忆化搜索+dp(较难)

dp跟记忆化搜索的关系十分密切

而记忆化搜索的主要难点并不在于dp，而在于DFS。

因此虽然题目可能较为困难，但dp的思路十分显然。

记忆化搜索就是，当一个点的结果可以由子结构的结果直接给出，那么我们就利用这一特点，用一种类似于dp的形式去搜索，避免反复搜索同样的结构即可。

P1113 杂务

思路：
这题一看就是拓扑排序。
考虑反向建边+dfs的dp，同《图的遍历》

DAG可直接用DFS+dp，不像“图的遍历”，还要调整顺序

拓扑排序的DFS做法好像就是DFS本体加上递归之前的一些操作？

最大值必定是树形结构的尽头

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
#include<bits/stdc++.h>
using namespace std;
const int MAXN=10005;
vector<int> points[MAXN];
int vis[MAXN];
int dp[MAXN];
int n;
int totoalMax=0;
void dfs(int i){//遍历下层，维护下层最大值，然后加上
    vector<int>& tos=points[i];
    int maxNum=0;
    for(int i=0,sz=tos.size();i<sz;i++){
        if(vis[tos[i]]){
            maxNum=max(dp[tos[i]],maxNum);
            continue;
        }
        dfs(tos[i]);
    }
    dp[i]+=maxNum;
    totoalMax=max(totoalMax,dp[i]);
    vis[i]=1;
    return;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,xt;
        cin>>x>>xt;
        dp[x]=xt;//初始化时间
        int temp;
        cin>>temp;
        while(temp){//建temp到x的反向边，防备反向遍历
            points[temp].push_back(x);
            cin>>temp;
        }
    }
    for(int i=n;i>0;i--){
        dfs(i);
    }
    cout<<totoalMax;
    return 0;
}


P4017 最大食物链计数

事实上，拓扑排序带给我们的最大启示就是要有寻找0入度的点的意识
在此题，我们可以通过读入边时标记入度，最后直接遍历全部点得到入度为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
#include<bits/stdc++.h>
using namespace std;
const int MOD=80112002;
const int MAXN=5005;
vector<int> p[MAXN];
int vis[MAXN],dp[MAXN];
int n,m,ans;
int dfs(int now){
    if(dp[now])
        return dp[now];
    vector<int>& tos=p[now];
    int len=tos.size();
    int tempAns=0;
    if(len==0){
        dp[now]=1;
        return 1;
    }
    for(int i=0;i<len;i++){
        tempAns=(tempAns+dfs(tos[i])%MOD)%MOD;
    }
    dp[now]=tempAns;
    return tempAns;
}
//寻找0入度的点：主函数循环+vis数组
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        //b吃a
        vis[a]=1;
        p[b].push_back(a);
    }
    for(int i=1;i<=n;i++){//无法确保1是0入度的
        if(vis[i])
            continue;
        ans=(ans+dfs(i)%MOD)%MOD;
    }
    cout<<ans;
    return 0;
}

P1434 [SHOI2002] 滑雪

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
#include<bits/stdc++.h>
using namespace std;
int row,col,my_map[105][105];
int dp[105][105],ans;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int dfs(int x,int y){//无后效性，可dp记忆化搜索：答案的来源不会影响到高点路径的选择
    if(dp[x][y])
        return dp[x][y];
    int longest=0;
    for(int i=0;i<4;i++){
        int x1=x+dx[i],y1=y+dy[i];
        if(x1<1||x1>row||y1<1||y1>col)
            continue;
        if(my_map[x1][y1]>=my_map[x][y])
            continue;
        longest=max(longest,dfs(x1,y1));
    }
    dp[x][y]=1+longest;
    return dp[x][y];
}
int main(){
    cin>>row>>col;
    for(int i=1;i<=row;i++){
        for(int j=1;j<=col;j++){
            cin>>my_map[i][j];
        }
    }
    for(int i=1;i<=row;i++){
        for(int j=1;j<=col;j++){
            ans=max(dfs(i,j),ans);
        }
    }
    cout<<ans;
    return 0;
}

背包dp

01背包

洛谷P1048采药

此为第三次做，代码能力明显提升，代码精简，思路清晰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int t,m,times[105],values[105];
int dp[105][1005];
int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>times[i]>>values[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=t;j++){//dp[i][j]是指前i件，用j钱的最优解
            if(j>=times[i]){//买得起当前件
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-times[i]]+values[i]);
            }else{
                dp[i][j]=dp[i-1][j];
            }
        }
    }
    cout<<dp[m][t];

    return 0;
}

尝试转化成一维滚动数组：
代码更短。
事实上，如果掌握了普通的二维背包，转化成一维滚动数组完全不难。
只需注意到，对于$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<bits/stdc++.h>
using namespace std;
int t,m,times[105],values[105];
int dp[1005];
int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++){
        cin>>times[i]>>values[i];
    }
    for(int i=1;i<=m;i++){
        for(int j=t;j>0;j--){//dp[i][j]是指前i件，用j钱的最优解
            if(j>=times[i]){//买得起当前件
                dp[j]=max(dp[j],dp[j-times[i]]+values[i]);
            }
            // else{
            //     dp[j]=dp[j];
            // }
        }
    }
    cout<<dp[t];

    return 0;
}

完全背包

P1616 疯狂的采药

完全背包模板：
暴力法：

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
#include<bits/stdc++.h>
using namespace std;
int t,m;
const int MAXN=1e4+5,MAXT=1e7+5;
int values[MAXN],times[MAXN];
int dp[MAXN][MAXT];



int main(){
    cin>>t>>m;
    for(int i=1;i<=m;i++)
        cin>>times[i]>>values[i];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=t;j++){//dp[i][j]表示在前i件物品中，用t的钱的最优解
            //完全背包，不知道要买几件
            //尝试枚举买的数量
            if(j<values[i]){
                dp[i][j]=dp[i-1][j];
                continue;
            }
            dp[i][j]=dp[i-1][j];
            //先储存不买的结果
            for(int k=1;k<=j/times[i];k++){//买k件
                dp[i][j]=max(dp[i][j],dp[i-1][j-k*times[i]]+k*values[i]);
            }
        }
    }
    cout<<dp[m][t];
    return 0;
}


暴力法思路较为清晰，但是所需空间太大，大概是100GB
$（1GB对应2.7 \times 10^{8}个int类型）$

空间优化：滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&times[i],&values[i]);
    for(int i=1;i<=m;i++){
        for(int j=t;j>=1;j--){
            if(j<times[i]){
                break;
            }//
            for(int k=1;k<=j/times[i];k++){//买k件
                dp[j]=max(dp[j],dp[j-k*times[i]]+k*values[i]);
            }
        }
    }
    cout<<dp[t];
    return 0;
}

时间优化：
解决时间问题：
在选定的i上，假设我现在可以购买k件，那么最优解从何得出呢？
是从买0件，买1件，买2件…买k-1件的最优解x与买不买第k件的最优解得出的。
而前k-1件的最优解同样符合此规律（最优子结构）

因此，状态转移方程是 $dp[j]=max(dp[j],dp[j-times[i]]+values[i])$
核心逻辑就是每次加钱，都比较一下这个时候买和这个时候不买会怎么样。
如果 j>=times[i]且j<2*times[i] ，那么就产生 买一件和不买 最优解 如果j>=2*times[i]，那么就产生买两件和买一件的最优解

简而言之，完全背包就是和同层的点去比，因为需要获取可能已经买了物品$i$的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int t,m;
const int MAXN=1e4+5,MAXT=1e7+5;
long long dp[MAXT];
int values[MAXN],times[MAXN];

int main(){
    scanf("%d%d",&t,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&times[i],&values[i]);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=t;j++){
            if(j<times[i])
                continue;
            dp[j]=max(dp[j],dp[j-times[i]]+values[i]);
        }
    }
    cout<<dp[t];
    return 0;
}

非完全背包

P1077 [NOIP 2012 普及组] 摆花

非完全背包的优化思路较难，暂时没有精力写
此题数据量较小，无需优化也可通过
从此题可以看出，多次背包的精髓在于，多开了一个选择的维度，相当于N个01背包的加和

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
#include<bits/stdc++.h>
using namespace std;
const int MOD=1e6+7;
int n,m,flower[105];
int dp[105][105];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>flower[i];
        dp[i][0]=1;
    }
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            //类完全背包，需要枚举买的数量
            dp[i][j]=dp[i-1][j];
            for(int k=1;k<=flower[i];k++){//在这里买k个
                if(j<k)
                    break;
                dp[i][j]+=dp[i-1][j-k];
                dp[i][j]%=MOD;
            }
        }   
    cout<<dp[n][m];
    return 0;
}