【AcWing】数位统计DP、树形DP、状态压缩DP、记忆化搜索

【AcWing】数位统计DP、树形DP、状态压缩DP、记忆化搜索

• • • 一、数位统计DP
    • 二、状态压缩DP
    • 三、树形DP
    • 四、记忆化搜索

一、数位统计DP

计数问题

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

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

1024 1025 1026 1027 1028 1029 1030 1031 1032

其中 0 出现 1010 次，1 出现 1010 次，2 出现 77 次，3 出现 33 次等等…

输入格式

输入包含多组测试数据。

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

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

输出格式

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

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

数据范围

0

输入样例：

1 10
44 497
346 542
1199 1748
1496 1403
1004 503
1714 190
1317 854
1976 494
1001 1960
0 0

输出样例：

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

分情况讨论！

[a,b]中，0~9出现的次数

若定义cnt(n,x): 求1~n中x出现的次数，则cnt(b,x)-cnt(a-1,x)即为所求

即求1~n中x出现的次数，n=abcdefg

分别求出1在每一位上出现的次数，再累加

例如：求x在第4位上出现的次数，即找到0<=abcxefg<=abcdefg的数字个数，分类讨论：

• 000~abc - 1（注意前导0的处理），x，000~999 情况数为abc*1000
• abc，x
  • d abcdefg，情况数是0
  • d=x，000~efg ，有efg+1种情况
  • d>x，000~999，有1000种情况

由此可以求出1在任意一位出现的次数，同理也可以求出其他数出现的次数，再累加即出现的总次数。

#include
#include
using namespace std;int dgt(int n){//计算整数n有多少位int res=0;while(n){res++;n/=10;}return res;
}int cnt(int n,int i){//计算从1~n的整数中数字i出现了多少次int res=0,d=dgt(n);for(int j=1;j<=d;j++){//从右到左第j位上数字i出现的次数）int p=pow(10,j-1);int l=n/p/10,r=n%p;//l和r是第j位左边和右边的整数（上述分析中的abc和efgint dj=n/p%10;//第j位的数字//计算第j位左边的整数小于l（000 ~ abc - 1）的情况if(i) res+=l*p;if(!i && l) res+=(l-1)*p;//如果i=0，左边高位（abc）不能全为0//计算第j位左边的整数等于l的情况//(i || l)表示i=0时，l不能为0(i不能出现在最高位)，因为这种数是不存在的if(dj>i && (i||l)) res+=p;if(dj==i && (i||l)) res+=r+1;}return res;
}int main(){int a,b;while(cin>>a>>b,a){if(a>b) swap(a,b);for(int i=0;i<=9;i++) cout<<cnt(b,i)-cnt(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

输入样例：

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

输出样例：

1
0
1
2
3
5
144
51205

当横向方格摆放位置确定后，纵向方格的位置也随之确定，故只需要求横向方格的摆放方案数。

f[i][j]：这种状态下总共的方案数

i表示摆放在第i列，j记录每一行这一列的摆放情况，哪些列有伸出来的小方格，j是一个二进制数
例如：

状态转移：

从i-1转移到i，如图，即从f[i-1][k]转移到f[i][j]

而能够转移（从前者能够变成后者）的条件：

1. 不能冲突（下一个方格的前端和上一个的后端重叠）： j&k==0
2. 所有连续的空白格需要是偶数 ：j|k不存在连续奇数个0

#include 
using namespace std;const int N=12,M=1<<N;int n,m;//n行m列
long long f[N][M];//防止溢出
bool st[M];//vector state[M];//二维数组记录合法的状态
vector<vector<int>> state(M); //两种写法等价:二维数组int main(){while(cin>>n>>m,n||m){ //读入n，m，并且不是两个0//预处理1：每列不能有奇数个连续的0for(int i=0;i<(1<<n);i++){int cnt=0;//连续奇数的个数bool isValid=true; //记录某种状态下是否有奇数个连续的0for(int j=0;j<n;j++){ //自上而下遍历这一列if((i>>j) & 1){//i>>j 位运算，表示i的二进制数的第j位//&1 判断这一位是否为1，如果是1则条件成立//如果这一位是1，则看前面连续的0的个数if(cnt & 1){//cnt&1 判断奇偶isValid=false; break;}cnt=0;//如果该位是1，且前面不是奇数个连续的0，则计数器清零//其实清不清零没有影响}//否则，该位是0，计数器+1else cnt++;}if(cnt&1) isValid=false; //最后一段判断连续0的奇偶st[i]=isValid; //状态i是否有奇数个连续的0}//预处理2：判断第i-2列伸出来的和第i-1列伸出去的是否冲突for(int j=0;j<(1<<n);j++){state[j].clear();//清空上次操作的遗留状态for(int k=0;k<(1<<n);k++){//对于第i列的所有状态if((j&k)==0 && st[j|k])//第i-2列伸出来的 和第i-1列伸出来的不能冲突(不能有重叠) //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++){//遍历每一列for(int j=0;j<(1<<n);j++){ //遍历当前列（第i列）所有状态jfor(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;}return 0;
}

最短Hamilton路径（旅行商问题）

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

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

输入格式

第一行输入整数 n。

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

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

输出格式

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

数据范围

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

输入样例：

5
0 2 4 5 1
2 0 6 5 3
4 6 0 8 3
5 5 8 0 5
1 3 3 5 0

输出样例：

18

分析：

0,1,2,3

0->1->2->3 18

0->2->1->3 20

具体路径对后续无影响，只关注走过了哪些点和最终停留在哪个点

两种路线的各种情况对应

1. 哪些点被用过
2. 目前停在哪个点上

f[state][j]=f[state_k][k]+weight[k][j], state_k = state 除掉j之后的集合,state_k 要包含k

用0和1来表示某个点是否存在，例如0，1，4个节点存在，则state=10011

1. 状态表示
   1. 集合：所有从0走到j，走过的所有点的情况是i的所有路径
   2. 属性：Min
2. 状态计算：0->...->k->j中k的所有情况
   

状态转移方程：f[i][j]=min(f[i][j],f[i^(1<

#include
#include
#include
using namespace std;const int N=20,M=1<<20;int n,f[M][N],weight[N][N];int main(){ios::sync_with_stdio(false);//加快cin的读入速度，但是scanf将会不能用。cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>weight[i][j];memset(f,0x3f,sizeof f);f[1][0]=0;//初始时在0号点for(int i=0;i<(1<<n);i++) //枚举所有状态for(int j=0;j<n;j++) //枚举当前到了哪一个点if(i>>j & 1)//判断i的第j位是否是1(也就是已经到达了j)for(int k=0;k<n;k++) //枚举到达j点的k点if((i^1<<j)>>k & 1)//状态i改变第j位之后，第k位是1（即状态i仍包含点k）//那么才可以从点k转移到点j// <<的优先级高于^//当然这个if也可以不加，因为如果i中去掉第j个点后，i中不包含k//那么f[i^(1<f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);//i^(1<//这里为1改成0，因为第一个if已经确保了i的第j位是1，即状态i一定经过了j点//而i^(1<//由于到达j的路径一定经过j，所以i的第j位为1的时候，f[i][j]才能被转移////最后结果应该是f[11..11(n个1)][n-1]//那么怎么构造n个1？ 可以直接用1<cout<<f[(1<<n)-1][n-1]<<endl;return 0;
}

#include
#include
#include
using namespace std;const int N=6010;int n;
int happy[N];
int h[N],e[N],ne[N],idx;//链表模拟树
int f[N][2];
bool has_father[N];//记录某个点是否有父节点void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}void dfs(int u){//更新f[u][0]和f[u][1]f[u][1]=happy[u];//如果选择当前节点，则先加上它的高兴度for(int i=h[u];i!=-1;i=ne[i]){//从u的子节点开始遍历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++) scanf("%d",&happy[i]);memset(h,-1,sizeof h);for(int i=0;i<n-1;i++){int a,b;cin>>a>>b;has_father[a]=true;add(b,a);}//遍历寻找根节点int root=1;while(has_father[root]) root++;dfs(root);//从根节点开始搜索//输出不选根节点和选根节点的最大值printf("%d\n",max(f[root][0],f[root][1]));return 0;
}

#include
#include
#include
using namespace std;const int N=310;
int n,m;
int h[N][N],f[N][N];int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};int dp(int x,int y){int &v=f[x][y];//引用，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化if(v!=-1) return v;//如果从这个点出发的最长长度已经被计算过了，则直接返回v=1;//v最小值是1for(int i=0;i<4;i++){int a=x+dx[i],b=y+dy[i];//枚举上下左右四个方向if(a>=1 && a<=n && b>=1 && b<=m &&h[a][b]<h[x][y])//判断是否合法v=max(v,dp(a,b)+1);//更新}return v;
}int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&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));printf("%d\n",res);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！