数位DP、状压DP、树形DP、记忆化搜索

目录一、数位DPAcWing 338. 计数问题二、状态压缩DPAcWing 291. 蒙德里安的梦想AcWing 91. 最短Hamilton路径三、树形DPAcWing 285. 没有上司的舞会四、记忆化搜索AcWing 901. 滑雪记忆化搜索DFS:纯递推DP:一、数位DPAcWing 338. 计数问题分类讨论的结果for(int i n-1 - !x; i0; i--){//!x, x0时不用考虑第一位 if(i n-1){ //第一种情况是000~abc-1, 不能是第一位 0 ~ -1 res get(n-1, i1)*power10(i);//i不用减1从0开始 if(!x) res - power10(i); //统计 0 时要把 “前导 0” 的情况全部减掉每位最高位是0的可能减掉 } if(num[i] x) resget(i-1, 0) 1; if(num[i] x) respower10(i); }#include bits/stdc.h using namespace std; vectorint num; int get(int l, int r){ int res 0; for(int i l; ir; i--){ res res*10 num[i]; } return res; } int power10(int x){ int res 1; for(int i 1; ix; i) res *10; return res; } int count(int n, int x){ if(!n) return 0; num.clear(); // 必须加清空上一次的数字 while(n){ num.push_back(n%10); n/10;//将n的所有位数从低到高存入数组 } n num.size(); int res 0; for(int i n-1 - !x; i0; i--){//!x, x0时不用考虑第一位 if(i n-1){ //第一种情况是000~abc-1, 不能是第一位 0 ~ -1 res get(n-1, i1)*power10(i);//i不用减1从0开始 if(!x) res - power10(i); //统计 0 时要把 “前导 0” 的情况全部减掉每位最高位是0的可能减掉 } if(num[i] x) resget(i-1, 0) 1; if(num[i] x) respower10(i); } return res; } int main(){ int a, b; while(cin a b , a || b){ if(a b) swap(a, b); for(int i 0; i10; i){ cout count(a, i) - count(b-1, i) ; } cout endl; } return 0; }二、状态压缩DPAcWing 291. 蒙德里安的梦想#include bits/stdc.h using namespace std; const int N 12, M 1 N; long long f[N][M];//前i-1列已经摆好切从i-1列伸出到i列所有的可能 //M是一个二进制数 bool st[M]; vectorint state[M]; int main(){ int n, m; while(cin n m, n||m){ //先把所有当前列格子中被填满的合法可能求出来 for(int i0; i 1n; i){ int cnt 0;//0的个数 bool is_val true; for(int j 0; jn; j){ if(i j 1){ if(cnt 1){ is_val false; break; } }else cnt ; } if(cnt 1) is_val false; st[i] is_val; } //把所有合法的相邻列找出来 for(int i 0; i 1n; i){ state[i].clear();//多重循环 for(int j 0; j 1n; j){ if((ij) 0 st[i|j]){ state[i].push_back(j);//这两个序列可以相邻 } } } memset(f, 0, sizeof f); f[0][0] 1; //从 第 0 列开始多出来一列f[m][0],这一列所有填满0的可能性就是答案 for(int i 1; im; i) { for(int j 0; j 1n; j){ for(auto k : state[j]){ f[i][j] f[i-1][k]; } } } cout f[m][0] endl; } return 0; }AcWing 91. 最短Hamilton路径从 0 出发 计算状态 00...1 ~11...1和包含的点数权值的最小值。可以用 i - 1j求出上一个点数的 状态用if(i j 1)判断这个状态是否包含该点。状态转移上一个相邻点的状态 w 现在点和状态取最小值。#include bits/stdc.h using namespace std; const int N 20, M 1 N; int f[M][N], w[N][N]; int n; int main(){ cin n; for(int i 0; in; i){ for(int j 0; jn; j) cin w[i][j]; } memset(f, 0x3f, sizeof f); f[1][0] 0;//点0的状态 0000001。 for(int i 0; i 1n; i){ //先枚举状态是因为要算 f [i][…]必须先算完所有比 i 小的状态 //要算f[011][1] 它依赖的是f[001][0] //如果先算点需要计算先知道所有以这个点结尾的状态 for(int j 0 ; jn; j){ if(i j 1){ for(int k 0; kn; k){ if(i-(1j) k 1){// ?? 为什么要减掉 //减掉 j是为了回到 “还没走到 j” 的前一个状态 f[i][j] min(f[i][j], f[i-(1j)][k] w[k][j] ); } } } } } cout f[(1n)-1][n-1]; return 0; }三、树形DPAcWing 285. 没有上司的舞会给每个节点u定义两个 DP 值f[u][0]不选u时以u为根的子树能获得的最大快乐值总和f[u][1]选u时以u为根的子树能获得的最大快乐值总和求某个节点的状态时需要先递归的求出每个子树的大小树的重心#include bits/stdc.h using namespace std; const int N 6010; int f[N][2]; int h[N], e[N], ne[N], idx; int happy[N]; bool is_root[N]; int 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][0], f[j][1]); f[u][1] f[j][0]; } } int main(){ cin n; memset(h, -1, sizeof h); for(int i 1; in; i) cin happy[i]; for(int i 1; in; i){ int a, b; cin a b; add(b, a); is_root[a] true; } int root 1; while(is_root[root]) root; dfs(root); cout max(f[root][0], f[root][1]); return 0; }四、记忆化搜索AcWing 901. 滑雪记忆化搜索每个都进行枚举、每个点的终点不一样在记忆化搜索的代码中起到关键作用的是记忆化数组f[i][j]。如果只是采用 dfs 暴搜的话每次在一个位置搜索完之后状态都不会被保留下次 dfs 还是重新开始就会有很多被算过的位置再重新计算。数据量大就会超时记忆化搜索就是 dfs 记忆化数组f[i][j]在算某一个位置时把它的所有路径上 所有算过的位置状态保存在数组f[i][j]里。if (f[x][y] ! -1) return f[x][y]; 下次求某个被算过的位置的状态时无需重新计算直接返回。是数组f[i][j]起到了记忆的作用。#include bits/stdc.h using namespace std; const int N 310; int f[N][N], 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){ int v f[x][y]; if(v ! -1) return v;//用来存储之前有的结果存储到能到的最低点最多到少步 v 1; //最少都有一格 for(int i 0; i4; i){//和dfs一样搜出这个点所有可能性 int a x dx[i], b y dy[i]; if(a 1 an b1 bm h[a][b] h[x][y]){ v max(v, dp(a, b) 1); } } return v; } int main(){ cin n m; memset(f, -1, sizeof f); for(int i 1; in; i) for(int j 1; jm; j) cin h[i][j]; int res 0; for(int i 1; in; i){//每个点都有可能是起点不是排好序的 for(int j 1; jm; j){ res max(res, dp(i, j)); } } cout res; return 0; }DFS:#include bits/stdc.h using namespace std; const int N 310; int h[N][N], n, m; int dx[] {-1,1,0,0}, dy[] {0,0,-1,1}; int ans; void dfs(int x, int y, int len) { ans max(ans, len); for(int i0;i4;i){ int axdx[i], bydy[i]; if(a1anb1bm h[a][b]h[x][y]) dfs(a,b,len1); } } int main(){ cinnm; for(int i1;in;i)for(int j1;jm;j)cinh[i][j]; for(int i1;in;i)for(int j1;jm;j)dfs(i,j,1); coutans; }纯递推DP:#include bits/stdc.h using namespace std; const int N 310; int h[N][N], f[N][N], n, m; struct Node{int x,y,val;}node[N*N]; bool cmp(Node a,Node b){return a.val b.val;} int dx[]{-1,1,0,0}, dy[]{0,0,-1,1}; int main(){ cinnm; int tot0; for(int i1;in;i) for(int j1;jm;j){ cinh[i][j]; node[tot]{i,j,h[i][j]}; f[i][j]1; } sort(node1,nodetot1,cmp); // 按高度从小到大 for(int i1;itot;i){//每个点从小到大排序 int xnode[i].x, ynode[i].y; for(int d0;d4;d){ int axdx[d], bydy[d]; if(a1||an||b1||bm)continue; if(h[a][b] h[x][y]) f[x][y] max(f[x][y], f[a][b]1); } } int ans0; for(int i1;in;i)for(int j1;jm;j)ansmax(ans,f[i][j]); coutans; }P2758 编辑距离 只有一条路径#include bits/stdc.h using namespace std; const int N 2010; int f[N][N]; char a[N], b[N]; int la, lb; int dfs(int x, int y){ if(x 0) return y; if(y 0) return x; int u f[x][y]; if(u ! -1) return u; u min({dfs(x-1, y)1, dfs(x, y-1)1, dfs(x-1, y-1) (a[x] ! b[y])}); return u; } int main(){ cin a 1 b 1; memset(f, -1, sizeof f); la strlen(a1); lb strlen(b1); cout dfs(la, lb) ; return 0; }