题单传送门
[P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216)[P1434 [SHOI2002]滑雪 - 洛谷](https://www.luogu.com.cn/problem/P1434)[P2196 [NOIP1996 提高组] 挖地雷 - 洛谷](https://www.luogu.com.cn/problem/P2196)[P4017 最大食物链计数 - 洛谷](https://www.luogu.com.cn/problem/P4017)[P1048 [NOIP2005 普及组] 采药 - 洛谷](https://www.luogu.com.cn/problem/P1048)[P1616 疯狂的采药 - 洛谷](https://www.luogu.com.cn/problem/P1616)[P1802 5 倍经验日 - 洛谷](https://www.luogu.com.cn/problem/P1802)[P1002 [NOIP2002 普及组] 过河卒 - 洛谷](https://www.luogu.com.cn/problem/P1002)
这是本蒟蒻刷动态规划专题的题目时，刷到的题单，题单在洛谷，算是简单动态规划入门题。在此献给大家。阿门！
P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
简单DP，递推公式很容易找到。dp[i][j]表示到达数字三角形第 i i i行的第 j j j个数的最大数字和。
其实只需要开一维数组即可，边输入边计算结果。
#includeP1434 [SHOI2002]滑雪 - 洛谷#include #include using namespace std; const int N = 1e3 + 10, INF = 0x3f3f3f3f; int tria[N][N]; //存数字三角形 int main() { int r; cin >> r; for(int i = 1; i <= r; i ++) for(int j = 1; j <= i; j ++) cin >> tria[i][j]; for(int i = 1; i <= r; i ++) for(int j = 1; j <= r; j ++) tria[i][j] += max(tria[i - 1][j - 1], tria[i - 1][j]); //递推公式 int ans = - INF; for(int i = 1; i <= r; i ++) ans = max(ans, tria[r][i]); cout << ans << endl; return 0; }
用深度优先搜索+记忆化搜索。深度优先搜索搜出来的结果用dis[i][j]来表示，意为以点 ( i , j ) (i, j) (i,j)为最高峰的最长距离。所有点都搜一遍，已经搜过的点的结果存入数组 d i s dis dis中。
很明显，因为低的不可能滑向高的，所以我们不需要再开一个数组去记录这个点是否走过。
#includeP2196 [NOIP1996 提高组] 挖地雷 - 洛谷#include #include using namespace std; const int N = 110; int row, col, ski[N][N], dis[N][N], dx[4] = {0, 0, -1, 1}, dy[4] = {-1, 1, 0, 0}; //ski记录滑雪场的高度，dis记录以每个点为最高峰的最长距离 int dfs(int n, int m) //深度优先搜索，记忆化搜索 { if(dis[n][m]) //算过的直接返回，因为算过的最长距离至少为1，不会为0 return dis[n][m]; for(int i = 0; i < 4; i ++) { int x = n + dx[i], y = m + dy[i]; if(0 < x && x <= row && 0 < y && y <= col && ski[n][m] > ski[x][y]) //四个方向和高度判断 dis[n][m] = max(dis[n][m], dfs(x, y)); //取最大值 } dis[n][m] ++; //还要加上自己本身的长度 return dis[n][m]; } int main() { cin >> row >> col; for(int i = 1; i <= row; i ++) for(int j = 1; j <= col; j ++) cin >> ski[i][j]; int ans = 0; //初始化最终结果 for(int i = 1; i <= row; i ++) for(int j = 1; j <= col; j ++) if(ans < dfs(i, j)) //取所有点中的最大值 ans = dis[i][j]; //前面已经算了一遍了，用数组存下了，这里可以直接用；写成dfs(i, j)也行 cout << ans << endl; return 0; }
对了，这题贼坑，图是有向图，不是无向图。其实这题，最后一个地窖只能被连接，不能连接别人。
用深度优先搜索即可。遍历每个点，以每个点为起点进行dfs。
#include#include #include using namespace std; const int N = 25; int n, mine[N], graph[N][N], path[N], ans[N], cnt, maxn; //mine记录地雷，graph记录图的边，即两个地雷之间的联系，path记录以每个点为起点的路径，ans是最终记录的路径，cnt记录最终挖了多少个地窖，maxn记录最终挖了多少个地雷 void dfs(int x, int step, int sum) //x记录现在位置，step记录走了几个点，sum记录挖的地雷总数 { int sign = 0; //记录是不是已经是叶子结点，即后面无结点 for(int i = x + 1; i <= n; i ++) if(graph[x][i]) { path[step + 1] = i; //不要写++ step，这里的step值不能变 dfs(i, step + 1, sum + mine[i]); sign = 1; //说明还有结点 } if(!sign) { if(maxn < sum) //交换地雷数、地窖数和路径 { maxn = sum; cnt = step; for(int i = 1; i <= cnt; i ++) ans[i] = path[i]; } } } int main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> mine[i]; for(int i = 1; i < n; i ++) for(int j = i + 1; j <= n; j ++) cin >> graph[i][j]; for(int i = 1; i <= n; i ++) //以每个点为起点开始dfs { path[1] = i; //记录起点 dfs(i, 1, mine[i]); } for(int i = 1; i <= cnt; i ++) cout << ans[i] << " "; cout << endl << maxn << endl; return 0; }
dp的做法。用一维dp[i]表示以 i i i为起点可以挖到的最多的地雷数，但是得倒序遍历。
#includeP4017 最大食物链计数 - 洛谷#include #include using namespace std; const int N = 25; int n, mine[N], graph[N][N], pre[N], dp[N]; //mine记录地雷，graph记录图的边，即两个地雷之间的联系，pre[i]记录每个i所指向的下一个儿子，这个儿子使得它的地雷数最多 int main() { cin >> n; for(int i = 1; i <= n; i ++) cin >> mine[i]; for(int i = 1; i < n; i ++) for(int j = i + 1; j <= n; j ++) cin >> graph[i][j]; dp[n] = mine[n]; //初始化 for(int i = n - 1; i > 0; i --) //倒序遍历每一点 { for(int j = i + 1; j <= n; j ++) //遍历所有儿子 if(graph[i][j]) { if(dp[i] < dp[j]) //选择地雷数最多的儿子，并记录下来 { dp[i] = dp[j]; pre[i] = j; } } dp[i] += mine[i]; //记得加上自身的地雷数 } int ans = 0, start; //ans记录最大地雷数，start记录ans对应的起点 for(int i = 1; i <= n; i ++) if(ans < dp[i]) { ans = dp[i]; start = i; } for(int i = start; i; i = pre[i]) //当i为0时，表示到头了，因为pre初始化就为0 cout << i << " "; cout << endl << ans << endl; return 0; }
这道题贼坑，不要光看样例，原本以为是按顺序的边的有向边，即1没有入度，最后一个数没有出度，事实证明我错了。这个跟结点编号没有关系，任何一个结点都有可能有出度和入度。
这道题还得拓扑排序。这里用了两种队列，其实差不多，思路都一样。用两个数组分别记录每个结点的入度和出度。入度为0的点入队列，出度为0的点计入结果。拓扑排序其实就是一种宽度优先搜索。
同时还要dp，用dp[i]表示从所有入度为0的结点出发到结点 i i i的食物链数目。
如何更新dp[i]？在遍历每个入度为0的结点的时候，我们把其指向的所有结点都更新一遍。递推公式为：dp[j] = (dp[i] + dp[j]) % mod（i -> j成立）。
手动写的队列：
#include#include #include using namespace std; const int N = 5e3 + 10, M = 5e5 + 10, mod = 80112002; //这里一定要记得N和M不一样，都要定义 int e[M], ne[M], h[N], idx; //三个数组的范围不一样！！！ int indeg[N], q[N], dp[N], outdeg[N]; int hh, tt = -1; int main() { memset(h, -1, sizeof h); //记得要初始化 int n, m; cin >> n >> m; while(m --) { int a, b; cin >> a >> b; indeg[b] ++; outdeg[a] = 1; ne[idx] = h[a], h[a] = idx, e[idx ++] = b; //一套组合操作 } for(int i = 1; i <= n; i ++) if(!indeg[i]) { q[++ tt] = i; //入队 dp[i] = 1; //记得赋初值 } int ans = 0; while(hh <= tt) //不为空队列 { int t = q[hh]; //取出队头 for(int i = h[t]; i != -1; i = ne[i]) //遍历以队头结点为入点的所有边 { int val = e[i]; //得到出点 indeg[val] --; //入度减一 if(!indeg[val]) q[++ tt] = val; //进队 dp[val] = (dp[val] + dp[t]) % mod; //及时更新 } if(!outdeg[t]) //出度为0，计入结果 ans = (ans + dp[t]) % mod; hh ++; //已遍历的结点丢掉 } cout << ans << endl; return 0; }
用STL中的queue：
#include#include #include #include using namespace std; const int N = 5e3 + 10, M = 5e5 + 10, mod = 80112002; //这里一定要记得N和M不一样，都要定义 int e[M], ne[M], h[N], idx; //三个数组的范围不一样！！！ int indeg[N], dp[N], outdeg[N]; queue q; int main() { memset(h, -1, sizeof h); int n, m; cin >> n >> m; while(m --) { int a, b; cin >> a >> b; indeg[b] ++; outdeg[a] = 1; ne[idx] = h[a], h[a] = idx, e[idx ++] = b; } for(int i = 1; i <= n; i ++) if(!indeg[i]) { q.push(i); dp[i] = 1; } int ans = 0; while(!q.empty()) { int t = q.front(); for(int i = h[t]; i != -1; i = ne[i]) { int val = e[i]; indeg[val] --; if(!indeg[val]) q.push(val); dp[val] = (dp[val] + dp[t]) % mod; } if(!outdeg[t]) ans = (ans + dp[t]) % mod; q.pop(); } cout << ans << endl; return 0; }
DFS(深度优先搜索)的做法：
注意，这里必须要记忆化搜索，否则就会TLE。
遍历所有入度为0的结点，深搜出以其为起点的所有最大食物链数目，累加取模得结果。
#includeP1048 [NOIP2005 普及组] 采药 - 洛谷#include #include using namespace std; const int N = 5e3 + 10, M = 5e5 + 10, mod = 80112002; //这里一定要记得N和M不一样，都要定义 int e[M], ne[M], h[N], idx; //三个数组的范围不一样！！！ int indeg[N], outdeg[N], paths[N]; //paths[i]记录从结点i出发到所有出度为0的结点的路径数 int dfs(int x) //从结点x出发到所有出度为0的结点的路径数 { if(!outdeg[x]) //到了最后一个结点，直接返回 return 1; if(paths[x]) //记忆化搜索 return paths[x]; int sum = 0; for(int i = h[x]; i != -1; i = ne[i]) //遍历所有入点 sum = (sum + dfs(e[i])) % mod; return paths[x] = sum; } int main() { memset(h, -1, sizeof h); int n, m; cin >> n >> m; while(m --) { int a, b; cin >> a >> b; indeg[b] = 1; outdeg[a] = 1; ne[idx] = h[a], h[a] = idx, e[idx ++] = b; //一套组合操作 } int ans = 0; for(int i = 1; i <= n; i ++) if(!indeg[i]) //遍历所有入度为0的结点，深搜出以其为起点的所有最大食物链数目，累加取模得结果 ans = (ans + dfs(i)) % mod; cout << ans << endl; return 0; }
01背包模板题。注意要初始化，以及倒序遍历即可。
#include#include #include using namespace std; const int N = 1e2 + 10, M = 1e3 + 10; int main() { int t, m; //t记录总的时间，m记录药材的种数 cin >> t >> m; int time[N], val[N]; //分别记录采药材的所需时间，药材的价值 for(int i = 1; i <= m; i ++) cin >> time[i] >> val[i]; int dp[M]; memset(dp, 0, sizeof dp); //初始化 for(int i = 1; i <= m; i ++) for(int j = t; j >= time[i]; j --) //记得要倒序遍历 dp[j] = max(dp[j], dp[j - time[i]] + val[i]); //递推方程 cout << dp[t] << endl; return 0; }
DFS+记忆化搜索做法：
参考大佬的笔记：P1048 [NOIP2005 普及组] 采药 - 洛谷
#includeP1616 疯狂的采药 - 洛谷#include #include using namespace std; const int N = 1e2 + 10, M = 1e3 + 10; int t, m; //t记录总的时间，m记录药材的种数 int tm[N], val[N]; //分别记录采药材的所需时间，药材的价值 int dp[N][M]; int dfs(int x, int remt) //剩余：remain/remainder //正在考虑第x个物品，还剩remt个空间 { if(x == m + 1) return 0; if(dp[x][remt] != -1) return dp[x][remt]; int ans1, ans2 = 0; //分为两种情况：不选或选；可能有空间却选不了，故初始化为0 ans1 = dfs(x + 1, remt); //不选，直接看下一个物品 if(remt >= tm[x]) ans2 = dfs(x + 1, remt - tm[x]) + val[x]; //选 return dp[x][remt] = max(ans1, ans2); } int main() { memset(dp, -1, sizeof dp); cin >> t >> m; for(int i = 1; i <= m; i ++) cin >> tm[i] >> val[i]; cout << dfs(1, t) << endl; return 0; }
完全背包模板题。注意要顺序枚举容量即可，还有本题要注意数据范围，防止MLE，还要开long long型数据。
#include#include #include using namespace std; typedef long long LL; const int N = 1e4 + 10, M = 1e7 + 10; int main() { int t, m; cin >> t >> m; int tm[N], val[N]; for(int i = 1; i <= m; i ++) cin >> tm[i] >> val[i]; LL dp[M]; memset(dp, 0, sizeof dp); for(int i = 1; i <= m; i ++) for(int j = tm[i]; j <= t; j ++) //顺序枚举容量 dp[j] = max(dp[j], dp[j - tm[i]] + val[i]); cout << dp[t] << endl; return 0; }
受到上一题的启发，这里用记忆化搜索试了一下，最高可以到80分，也就是说当 N ∗ M N * M N∗M太大时，会MLE。故得看情况使用。
这种背包dp，深搜的顺序不要紧，但有的题会有关系。
#includeP1802 5 倍经验日 - 洛谷#include #include using namespace std; const int N = 1e4 + 10, M = 1e7 + 10; int t, m; //t记录总的时间，m记录药材的种数 int tm[N], val[N]; //分别记录采药材的所需时间，药材的价值 int dp[N][M]; int dfs(int x, int remt) //剩余：remain/remainder //正在考虑第x个物品，还剩remt个空间 { if(x == m + 1) return 0; if(dp[x][remt] != -1) return dp[x][remt]; int ans1, ans2 = 0; //分为两种情况：不选或选；可能有空间却选不了，故初始化为0 ans1 = dfs(x + 1, remt); //不选，直接看下一个物品 for(int i = 1; remt >= i * tm[x]; i ++) ans2 = max(ans2, dfs(x + 1, remt - i * tm[x]) + i * val[x]); return dp[x][remt] = max(ans1, ans2); } int main() { memset(dp, -1, sizeof dp); cin >> t >> m; for(int i = 1; i <= m; i ++) cin >> tm[i] >> val[i]; cout << dfs(1, t) << endl; return 0; }
01背包模板题。这里有一维做法，二维做法以及记忆化搜索法。题目数据有错，记得开long long。
二维：理解题意，不选也有值可以加，建立正确的状态转移方程。
#include#include #include using namespace std; typedef long long LL; const int N = 1e3 + 10; LL dp[N][N]; int main() { int n, x; cin >> n >> x; int lose[N], win[N], use[N]; for(int i = 1; i <= n; i ++) cin >> lose[i] >> win[i] >> use[i]; for(int i = 1; i <= n; i ++) for(int j = 0; j <= x; j ++) //这里和二维不一样 { dp[i][j] = dp[i - 1][j] + lose[i]; //先初始化 if(use[i] <= j) //符合条件才更新 dp[i][j] = max(dp[i][j], dp[i - 1][j - use[i]] + win[i]); } cout << 5 * dp[n][x] << endl; return 0; }
一维滚动：
首先，呈递一个错误代码，得40分。具体原因是，数据中use可能为0。当用二维数组表示时就不会出错；用一维滚动数组时就会出错。
#include#include #include using namespace std; typedef long long LL; const int N = 1e3 + 10; LL dp[N]; int main() { int n, x; cin >> n >> x; int lose[N], win[N], use[N]; for(int i = 1; i <= n; i ++) cin >> lose[i] >> win[i] >> use[i]; for(int i = 1; i <= n; i ++) for(int j = x; j >= 0; j --) //这里和一维不一样 { dp[j] += lose[i]; if(use[i] <= j) dp[j] = max(dp[j], dp[j - use[i]] + win[i]); //数据有陷阱，use可能为0，则不满足下标递减的规律 } cout << 5 * dp[x] << endl; return 0; }
正确代码：
#include#include #include using namespace std; typedef long long LL; const int N = 1e3 + 10; LL dp[N]; int main() { int n, x; cin >> n >> x; int lose[N], win[N], use[N]; for(int i = 1; i <= n; i ++) cin >> lose[i] >> win[i] >> use[i]; for(int i = 1; i <= n; i ++) //这里和一维不一样 { int j = x; //把它们分成两部分就不怕了 for(j = x; j >= use[i]; j --) dp[j] = max(dp[j] + lose[i], dp[j - use[i]] + win[i]); for(; j >= 0; j --) dp[j] += lose[i]; } cout << 5 * dp[x] << endl; return 0; }
记忆化搜索法：
#includeP1002 [NOIP2002 普及组] 过河卒 - 洛谷#include #include using namespace std; typedef long long LL; const int N = 1e3 + 10; int n, x; int lose[N], win[N], use[N]; LL dp[N][N]; LL dfs(int pos, int remx) //剩余的x；正在考虑第pos个位置的物品，还剩remx个空间 { if(pos == n + 1) return 0; if(dp[pos][remx] != -1) return dp[pos][remx]; LL ans1, ans2 = 0; //分三种情况，不能选，能选但不选，能选且选 ans1 = dfs(pos + 1, remx) + lose[pos]; //ans1先记录不选或者选不了的情况，后面可以对最终结果进行更改 if(use[pos] <= remx) //如果可以选 ans2 = max(ans1, dfs(pos + 1, remx - use[pos]) + win[pos]); //分两种情况 return dp[pos][remx] = max(ans1, ans2); } int main() { cin >> n >> x; for(int i = 1; i <= n; i ++) cin >> lose[i] >> win[i] >> use[i]; memset(dp, -1, sizeof dp); cout << 5 * dfs(1, x) << endl; return 0; }
二维dp做法：
如果不考虑马的拦截，那么就有递推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]成立。dp[i][j]表示从点(0, 0)到点(i, j)路径数，那么它等于原点到它左边的点的路径数+原点到它上面的点的路径数。
现在考虑马的拦截，我们让马的拦截点的dp值始终为0（因为它这个点不可到达），这样就不会影响别的点的dp值了。上述递推公式可以照用。所以在dp之前应该预先算出马的拦截点，并记录下来，这里用flag来记录，其值为1，其余可到达的点为0。然后在dp之前，初始化。从小到大一层一层递推，每一层从左到右，遇见马的拦截点，直接跳过。对了，我还让坐标从1开始，这样有利于递推。
#include#include #include using namespace std; typedef long long LL; const int N = 25; LL dp[N][N], flag[N][N]; int dx[9] = {-2, -2, -1, -1, 0, 1, 1, 2, 2}, dy[9] = {-1, 1, -2, 2, 0, -2, 2, -1, 1}; //一头马对应着九个位置，这里是两个坐标轴的变化；flag记录马的拦截点，为1，其余为0。 int main() { int n, m, hsx, hsy; cin >> n >> m >> hsx >> hsy; for(int i = 0; i < 9; i ++) //事先算出马的拦截点 if(0 < hsx + 1 + dx[i] && 0 < hsy + 1 + dy[i]) flag[hsx + 1 + dx[i]][hsy + 1 + dy[i]] = 1; dp[1][1] = 1; //初始化 for(int i = 1; i <= n + 1; i ++) for(int j = 1; j <= m + 1; j ++) if(!flag[i][j]) //遇见拦截点就走，保证拦截点的dp值为0 dp[i][j] += dp[i - 1][j] + dp[i][j - 1]; //这里的+=主要对点(1, 1)起作用 cout << dp[n + 1][m + 1] << endl; //下标在题意的基础上加一 return 0; }
记忆化搜索法：
受到大佬的影响，反正以后dp能解决的问题，我一定要用DFS+记忆化搜索试试。
不过要注意，题目的原点是(0, 0)，终点是(n, m)；我这里的原点是(1, 1)，终点是(n + 1, m + 1)。
dp[i][j]的含义和上述相同，递推公式也同上。
#include#include #include using namespace std; typedef long long LL; const int N = 25; LL dp[N][N]; int flag[N][N]; int dx[9] = {-2, -2, -1, -1, 0, 1, 1, 2, 2}, dy[9] = {-1, 1, -2, 2, 0, -2, 2, -1, 1}; //一头马对应着九个位置，这里是两个坐标轴的变化；flag记录马的拦截点，为1，其余为0。 LL dfs(int x, int y) { if(dp[x][y] != -1) //记忆化搜索，直接返回 return dp[x][y]; if(flag[x][y] || !x || !y) //马的拦截点和超出范围的点的dp值均为0 return dp[x][y] = 0; return dp[x][y] = dfs(x - 1, y) + dfs(x, y - 1); //递推公式 } int main() { int n, m, hsx, hsy; cin >> n >> m >> hsx >> hsy; for(int i = 0; i < 9; i ++) //事先算出马的拦截点 if(0 < hsx + 1 + dx[i] && 0 < hsy + 1 + dy[i]) flag[hsx + 1 + dx[i]][hsy + 1 + dy[i]] = 1; memset(dp, -1, sizeof dp); dp[1][1] = 1; //初始化 cout << dfs(n + 1, m + 1) << endl; return 0; }
