- 重难点：【p3160】局部最小值
-
重难点：【p3736】字符合并
状压DPの一般习题
T1：【p2704】炮兵阵地
- 一个N*M的地图，每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。
- 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。
- 每个部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
- 两支炮兵部队之间不能互相攻击，即任何炮兵部队都不在其他部队的攻击范围内。
- 在整个地图区域内最多能够摆放多少我军的炮兵部队。
这题确实是状压dp的经典啊...确实细节也算不太好处理...
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> using namespace std; //用每个m位二进制数表示一行的状态： //每个二进制数的第k位为1表示在第k列上放置部队。 /*【p2704】炮兵阵地 一个N*M的地图，每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。 每个部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 两支炮兵部队之间不能互相攻击，即任何炮兵部队都不在其他部队的攻击范围内。 在整个地图区域内最多能够摆放多少我军的炮兵部队。*/ //预处理出集合S，储存“相邻两个1的距离不小于3”的所有M位二进制数。 int sums[(1<<10)]; //sums[x]表示x的二进制表示中1的个数//int ff[109][1<<11][1<<11]; //2048*2048*109??? ---> 所以要用滚动数组啊qwq //f[i][j][k]表示第i-1行的状态是j，第i行状态是k时，前i行最多放置的炮兵数。 int f[3][(1<<11)][(1<<11)]={0}; //【滚动数组】记录前两行的状态即可，即(%3=)0,1,2 。 int n,m,a[109],anss=0; //a[109]记录每行的初始可行状态(是二进制数转化为十进制的数) void reads(int &x){ int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; } int getsum(int S){ //当前状态 S 里面包含几个 1 int tot=0; while(S){if(S&1) tot++; S>>=1;} return tot; } //【坑点！！】这个一定要写成函数，要不然会TLE... int main(){ reads(n); reads(m); char ss; for(int i=0;i<n;i++) //注意，状压DP中最好都用0开始 for(int j=0;j<m;j++) //用a[i]记录每行的初始可行状态 cin>>ss,a[i]<<=1,a[i]+=(ss=='H'?1:0); //二进制数a[i]每次向前移一位，记录第i行中障碍的位置 memset(sums,0,sizeof(sums)); //记录每种行状态要放置的部队数 for(int i=0;i<(1<<m);i++) sums[i]=getsum(i); for(int i=0;i<(1<<m);i++) //【预处理】初始化第一行(行数编号是0) if(!(i&a[0] || (i&(i<<1)) || (i&(i<<2)))) //判断‘行放置情况’有没有冲突 f[0][i][0]=sums[i]; //第一行要特殊判定，相当于赋初始值 for(int j=0;j<(1<<m);j++) //【预处理】初始化第二行(行数编号是1) for(int k=0;k<(1<<m);k++) //j是上一行,k是这一行 if(!(j&k || j&a[0] || k&a[1] || (j&(j<<1)) || (j&(j<<2)) || (k&(k<<1)) || (k&(k<<2)) ) ) f[1][j][k]=sums[k]+sums[j]; //第二行要特殊判定(因为没有2-2=0行) for(int i=2;i<n;i++) //枚举行数 for(int j=0;j<(1<<m);j++){ //【预处理】“相邻两个1的距离不小于3”的所有M位二进制数 if(j&a[i-1] || (j&(j<<1)) || (j&(j<<2))) continue; //‘行放置状态’冲突 for(int k=0;k<(1<<m);k++){ //j是上一行(i-1),k是这一行(i) if(k&a[i] || j&k || (k&(k<<1)) || (k&(k<<2))) continue; //特判 for(int FL=0;FL<(1<<m);FL++){ //FL是上上一行 if(FL&j || FL&k || FL&a[i-2] || (FL&(FL<<1)) || (FL&(FL<<2))) continue; f[i%3][j][k]=max(f[i%3][j][k],f[(i-1)%3][FL][j]+sums[k]); //转移:max放置数 } } } for(int j=0;j<(1<<m);j++) for(int k=0;k<(1<<m);k++) anss=max(anss,f[(n-1)%3][j][k]); cout<<anss<<endl; return 0; //倒数两行可以是任意状态(可行才会有值),求出最终的max放置个数 }
后来自己重新打了一遍，果然还是把循环里的 j++ 写成了 i++ ...
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<vector> using namespace std; //用每个m位二进制数表示一行的状态： //每个二进制数的第k位为1表示在第k列上放置部队。 /*【p2704】炮兵阵地 一个N*M的地图，每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示）。 在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）。 每个部队能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。 两支炮兵部队之间不能互相攻击，即任何炮兵部队都不在其他部队的攻击范围内。 在整个地图区域内最多能够摆放多少我军的炮兵部队。*/ int sums[(1<<10)]; //sums[x]表示x的二进制表示中1的个数 int f[3][(1<<11)][(1<<11)]={0}; //【滚动数组】记录前两行的状态即可，即(%3=)0,1,2 。 int n,m,a[109],anss=0; //a[109]记录每行的初始可行状态(是二进制数转化为十进制的数) void reads(int &x){ int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; } int get_cnt(int S){ //当前状态 S 里面包含几个 1 int tot=0; while(S){if(S&1) tot++; S>>=1;} return tot; } //【坑点！！】这个一定要写成函数，要不然会TLE... int main(){ reads(n); reads(m); char ss; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>ss,a[i]<<=1,a[i]+=(ss=='H'?1:0); for(int i=0;i<(1<<m);i++) sums[i]=get_cnt(i); //先处理出sums for(int i=0;i<(1<<m);i++) for(int j=0;j<(1<<m);j++) if( ! ( (i&a[1]) || (j&a[0]) || (i&j) || (i&(i<<1)) //只需预处理第二行 || (i&(i<<2)) || (j&(j<<1)) || (j&(j<<2)) ) ) f[1][i][j]=sums[j]+sums[i]; for(int i=2;i<n;i++) //注意这里要从i=2开始 for(int j=0;j<(1<<m);j++){ //上一行 if(j&a[i-1]||(j&(j<<1))||(j&(j<<2))) continue; for(int k=0;k<(1<<m);k++){ if(j&k) continue; if(k&a[i]||(k&(k<<1))||(k&(k<<2))) continue; for(int LS=0;LS<(1<<m);LS++){ if((j&LS)||(k&LS)) continue; if(LS&a[i-2]||(LS&(LS<<1))||(LS&(LS<<2))) continue; f[i%3][k][j]=max(f[i%3][k][j],f[(i-1)%3][j][LS]+sums[k]); } } } for(int j=0;j<(1<<m);j++) for(int k=0;k<(1<<m);k++) anss=max(anss,f[(n-1)%3][j][k]); cout<<anss<<endl; return 0; //倒数两行可以是任意状态(可行才会有值),求出最终的max放置个数 }
T2：【p1896】互不侵犯
- 国王能攻击到它上下左右、以及左上左下右上右下八个方向上一个格子。
- 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。
f[i][j][s]表示考虑到了第i行，已经放置了j个国王，上一行的放置情况为s。
枚举这一行的放置情况t。要满足：t是合法的，并且可以与s作相邻行。
转移方程：f[i][j+count(t)][t]+=f[i-1][j][s]; //【方案数DP】+【状压DP】
#include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <queue> #include <stack> using namespace std; typedef long long ll; typedef unsigned long long ull; /*【洛谷p1896】互不侵犯 国王能攻击到它上下左右、以及左上左下右上右下八个方向上一个格子。 在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。*/ //【方案数DP】+【状压DP】 //f[i][j][s]表示考虑到了第i行，已经放置了j个国王，上一行的放置情况为s。 //枚举这一行的放置情况t。要满足：t是合法的，并且可以与s作相邻行。 //转移方程：f[i][j+count(t)][t]+=f[i-1][j][s]; //count(t)表示t的二进制表示下1的数量，就是这一行的国王数。 void reads(int &x){ int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; } int n,m,cnt,MAX; ll f[20][400][1000]; int can[1000],sums[2000]; //行能到达的状态，每个状态的国王数 int get_cnt(int x){ int ret=0; while(x) ret+=(x&1),x>>=1; return sums[cnt]=ret; } int main(){ int l,x,y; ll ans=0; reads(n),reads(m); MAX=(1<<n)-1; //二进制状态总数 for(int i=0;i<=MAX;i++) //预处理可行的‘行状态’，初始化dp数组的第一行 if(!(i&(i<<1))) can[++cnt]=i,f[1][get_cnt(i)][cnt]=1; for(int i=2;i<=n;i++) for(int j=1;j<=cnt;j++){ x=can[j]; //此行的状态 for(int k=1;k<=cnt;k++){ y=can[k]; //下一行的状态 if((x&y)||(x&(y<<1))||(x&(y>>1))) continue; //不能相邻 for(int l=0;l<=m;l++) f[i][l+sums[j]][j]+=f[i-1][l][k]; //枚举之前已经放的个数 } //转移：f[i][count(t)+上行总国王数][状态]+=f[i-1][上行总国王数][上行状态]; } for(int i=1;i<=cnt;i++) ans+=f[n][m][i]; printf("%lld ",ans); }
T3：【p3052】摩天大楼的奶牛
- 给出n个物品，体积分别为w[i]，现把其分成若干组，
- 要求每组总体积<=W，问最小分组。(n<=18)。
f[i][j]表示已经分了i组，n个物品的选择状态是j时，当前组中的min体积。
如果存在d[i][j]这种方案，枚举不属于状态j的物品k，转移到d[i/i+1][j&(1<<k)]。
从前往后搜索，得到第一个存在j=2^n-1的方案即可。
#include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <stack> #include <queue> #include <set> using namespace std; typedef long long ll; /*【p3052】摩天大楼的奶牛 给出n个物品，体积分别为w[i]，现把其分成若干组， 要求每组总体积<=W，问最小分组。(n<=18)。 */ /*【分析】状压DP f[i][j]表示已经分了i组，n个物品的选择状态是j时，当前组中的min体积。 如果存在d[i][j]这种方案，枚举不属于状态j的物品k，转移到d[i/i+1][j&(1<<k)]。 从前往后搜索，得到第一个存在j=2^n-1的方案即可。 */ void reads(int &x){ int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; } int f[20][(1<<20)]; int n,m,w[20]; int main(){ reads(n); reads(m); for(int i=0;i<n;i++) reads(w[i]); for(int i=0;i<=n;i++) //分组数 for(int j=0;j<=(1<<n)-1;j++) //每个状态 f[i][j]=0x3f3f3f3f; //初始化为+∞ for(int i=0;i<=n;i++) f[1][1<<i]=w[i]; //边界：第1组放任意一个物品 for(int i=0;i<=n;i++) //组数从0~n for(int j=0;j<=(1<<n)-1;j++) if(f[i][j]!=0x3f3f3f3f) //如果该状态存在【存在性】 for(int k=0;k<n;k++){ //枚举不属于状态j的物品k if((j&(1<<k))!=0) continue; //k属于j，舍去 ↓↓↓判断是否更新f[i][j|(1<<k)] if(f[i][j]+w[k]<=m) f[i][j|(1<<k)]=min(f[i][j|(1<<k)],f[i][j]+w[k]); else f[i+1][j|1<<k]=w[k]; //上一组存不下，要多存一组 } for(int i=0;i<=n;i++) //组数从小到大 if(f[i][(1<<n)-1]!=0x3f3f3f3f) //只要有满足全选的状态的方案 { printf("%d ",i); break; } //输出组数并退出 }
T4：【p3622】动物园
- 每个小朋友站在大围栏圈的外面，可以看到连续的 5 个围栏。
- 你得到了所有小朋友喜欢和害怕的动物信息。
- 当下面两处情况之一发生时，小朋友就会高兴：
- 1.至少有一个他害怕的动物被移走
- 2.至少有一个他喜欢的动物没被移走
- 输出一个数，表示最多可以让多少个小朋友高兴。
考虑到不同的小朋友看见的围栏范围可能相同，要预处理num[pos][s]：
表示从第pos个开始的五个围栏移走状态为s（全满则为15=2^4-1）时，满意的人数。
f[i][s]表示‘枚举到第i个围栏,且[i,i+5]的围栏移走状态为s’时的最多满意人数。
则f[i][s]可以由第i-1个围栏移走和不移走两种状态转移得来：
- f[i][s]=max(f[i−1][(s&15)<<1],f[i−1][(s&15)<<1∣1])+num[i][s]；
注意：在dp之前先枚举前五个的状态state。避免环形问题。
那么此时必须满足s=state才是有效状态，更新答案。//【状压DP】【环形问题】
#include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <stack> #include <queue> #include <set> using namespace std; typedef long long ll; /*【p3622】动物园 每个小朋友站在大围栏圈的外面，可以看到连续的 5 个围栏。 你得到了所有小朋友喜欢和害怕的动物信息。 当下面两处情况之一发生时，小朋友就会高兴： 1.至少有一个他害怕的动物被移走 2.至少有一个他喜欢的动物没被移走 输出一个数，表示最多可以让多少个小朋友高兴。 */ /* 考虑到不同的小朋友看见的围栏范围可能相同，要预处理num[pos][s]： 表示从第pos个开始的五个围栏移走状态为s（全满则为15=2^4-1）时，满意的人数。 f[i][s]表示‘枚举到第i个围栏,且[i,i+5]的围栏移走状态为s’时的最多满意人数。 则f[i][s]可以由第i-1个围栏移走和不移走两种状态转移得来： f[i][s]=max(f[i−1][(s&15)<<1],f[i−1][(s&15)<<1∣1])+num[i][s]； 注意：在dp之前先枚举前五个的状态state。避免环形问题。 那么此时必须满足s=state才是有效状态，更新答案。//【状压DP】【环形问题】 */ void reads(int &x){ int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; } const int N=50019; int n,m,ans,f[N][40],num[N][40]; int main(){ reads(n),reads(m); for(int i=1,E,a,b,t;i<=m;i++){ reads(E),reads(a),reads(b); int l=0,d=0; //分别记录不喜欢的和喜欢的对应的状态 for(int j=1;j<=a;j++) //不喜欢的，相应位置上为1 reads(t),t=(t-E+n)%n,l|=1<<t; for(int j=1;j<=b;j++) //喜欢的，相应位置上为1 reads(t),t=(t-E+n)%n,d|=1<<t; for(int j=0;j<32;j++) //num表示‘从E开始的5个围栏移走状态为s时,满意的人数’ if((j&l)||(~j&d)) num[E][j]++; //j为要选择移走的状态 } for(int i=0;i<32;i++){ memset(f[0],128,sizeof(f[0])),f[0][i]=0; //初始-inf,设置dp起点 for(int j=1;j<=n;j++) //枚举围栏数 for(int s=0;s<32;s++) //枚举移走状态，从上一位置移走和不移走两种状态转移 f[j][s]=max(f[j-1][(s&15)<<1],f[j-1][(s&15)<<1|1])+num[j][s]; if(ans<f[n][i]) ans=f[n][i]; //更新ans } printf("%d ",ans); return 0; //输出ans：最多的满意人数 }
T5：【p1523】旅行商
- 现在笛卡尔平面上有n(n<=1000)个点，每个点的坐标为(x,y)(为整数)。
- 任意两点之间到达的代价为这两点的欧几里德距离，求最短bitonic tour(双调旅程)。
- 即从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。
#include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <stack> #include <queue> #include <set> using namespace std; typedef long long ll; /*【洛谷p1523】旅行商（NPC难题简化版） 现在笛卡尔平面上有n(n<=1000)个点，每个点的坐标为(x,y)(为整数)。 任意两点之间相互到达的代价为这两点的欧几里德距离，求最短bitonic tour(双调旅程)。 即从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。 */ void reads(int &x){ int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} x*=fx; } /* int dist[50][50],n,dp[1<<12][20]; int main(){ while(scanf("%d",&n)!=EOF&&n!=0){ n++; for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&dist[i][j]); for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]=dist[i][k]+dist[k][j]; for(int i=0;i<(1<<12);i++) for(int j=0;j<20;j++) dp[i][j]=2e9; dp[0][0]=0; for(int i=1;i<(1<<n);i++) for(int j=0;j<n;j++) //枚举状态j作为终点的情况 if(((1<<j)&i)) for(int k=0;k<n;k++) //枚举上一次的位置k if( ! ( (i-(1<<j)) || ((1<<k)&(i-(1<<j))) ) ) // k -> j dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+dist[k][j]); cout<<dp[(1<<n)-1][0]<<endl; //限定终点0 } } */ //以上是点少的时候的状压解法，洛谷的题目是不能过的 //旅行商问题，不过要求了只能单向走，所以可以简化。 //双向的问题转化为：假设有两个人一起从西往东走，走过的点不能重复。 //f[i][j]表示第一个人走到i，第二个人走到j的最短路径。 //能够发现，第j+1个点不是被第一个人走，就是被第二个人走。 //方程1：f[i][j+1]=min{f[i][j]+d[j][j+1]} //方程2：f[j][j+1]=min{f[i][j]+d[i][j+1]} struct node{ double x,y; }a[1019]; double d[1019][1019],f[1019][1019]; bool cmp(node a,node b){ return a.x<b.x; } double dist(node a,node b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); } int main(){ int n; reads(n); for(int i=0;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); sort(a,a+n,cmp); for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) d[i][j]=dist(a[i],a[j]),f[i][j]=1e30; //预处理+初始化 f[0][1]=d[0][1]; //dp起点 for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) //j+1点不是被第一个人走，就是被第二个人走 f[i][j+1]=min(f[i][j+1],f[i][j]+d[j][j+1]), //被j走 f[j][j+1]=min(f[j][j+1],f[i][j]+d[i][j+1]); //被i走 double ans=1e30; //当一个人走到终点时， for(int j=0;j<n-1;j++) //枚举另一个人的最后一步 ans=min(ans,f[j][n-1]+d[j][n-1]); printf("%.2lf ",ans); }
T6：【UVa1252】20个问题
- 有n个物体，m（m≤11）个特征。每个物体用一个m位01串表示特征具备与否。
- 我在心里想一个物体（一定是这n个物体之一），你来猜，每次可以询问一个特征。
- 然后我会告诉你是否具备，如果你采用最优策略，最少需要询问几次能保证猜到？
用集合s表示已经询问的特征集，a表示已确认具备的特征集，s中除去a的特征是不具备的。
设f[s][a]表示已经询问了特征集s，其中W所具备的特征集为a时，还需要询问的最小次数。
枚举下一次提问的对象是特征k，则询问次数为：【每次取考虑所有的k得到的最小值】
f[s+{k}][a+{k}] = max{ f[s+{k}][a+{k}] , f[s+{k}][a] }+1 //a具备或不具备，每次询问次数+1。
先把满足每个s和a条件的{物体个数}统计出来，记录在cnt[s][a] //预处理
- 其中 s：我们已经问过的特性集； a：具备的特征集。
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } /*【UVa1252】20个问题 有n（n≤128）个物体，m（m≤11）个特征。每个物体用一个m位01串表示特征具备与否 我在心里想一个物体（一定是这n个物体之一），你来猜，每次可以询问一个特征 然后我会告诉你是否具备，如果你采用最优策略，最少需要询问几次能保证猜到？ */ /*【分析】用集合s表示已经询问的特征集，a表示已确认具备的特征集，s中除去a的特征是不具备的。 设f[s][a]表示已经询问了特征集s，其中W所具备的特征集为a时，还需要询问的最小次数。 枚举下一次提问的对象是特征k，则询问次数为：【每次取考虑所有的k得到的最小值】 f[s+{k}][a+{k}] = max{ f[s+{k}][a+{k}] , f[s+{k}][a] }+1 //a具备或不具备，每次询问次数+1。*/ /* 先把满足每个s和a条件的{物体个数}统计出来，记录在cnt[s][a] //预处理 */ // s:我们已经问过的特性集； a:具备的特征集 const int N=11;//物体数 int kase=0,n,m; char objects[129][129]; int vis[1<<N][1<<N],f[1<<N][1<<N]; //f[s][a]表示满足s、a时，还需要询问的最小次数 int cnt[1<<N][1<<N]; //满足s和a条件的{物体个数} int dp(int s,int a){ if(cnt[s][a]<=1) return 0; //找到了，不用问了 if(cnt[s][a]==2) return 1; //二选一，还需要一次 int& ans=f[s][a]; //记录f[s][a]到ans中，便于计算 if(vis[s][a]==kase) return ans; //记忆化搜索 vis[s][a]=kase; //巧妙：对于每一组，不用清空vis ans=m; for(int k=0;k<m;k++) if(!(s&(1<<k))){ //枚举特征，找s中没包含的一个特征 int s2=s|(1<<k),a2=a|(1<<k); //计算特征k对s、a的改变 if(cnt[s2][a2]>=1&&cnt[s2][a]>=1) //还需要特殊判断 ans=min(ans,max(dp(s2,a2),dp(s2,a))+1); } // k为真，为假的两种情况 return ans; //满足集合的最少询问次数 } int main(){ while(scanf("%d%d",&m,&n)==2&&n&&m){ kase++; //↓输入每个物品的状态 for(int i=0;i<n;i++) scanf("%s",objects[i]); for(int s=0;s<(1<<m);s++){ //枚举所有状态 for(int a=s;a;a=(a-1)&s) cnt[s][a]=0; cnt[s][0]=0; //清空 } for(int i=0;i<n;i++){ int features=0; //每个物品 for(int f=0;f<m;f++) //对于某个特征 if(objects[i][f]=='1') features|=(1<<f); //记录它的所有1 for(int s=0;s<(1<<m);s++) cnt[s][s&features]++; //求交集，得到物品i含有的状态a } printf("%d ",dp(0,0)); //cnt记录相同特征的物品出现的次数 } }
T7：【p1278】单词游戏
- 在词典中进行单词接龙，问能接到的最大长度。
f[S][c] 即选择状态为S、且末位字符为c时是否可行（bool）
因为单词只和首尾有关，所以转移的时候可以巧妙地用到 a[last].r=a[i].l;
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; /*【p1278】单词游戏 词典中单词接龙，问能接到的最大长度。*/ //f[S][c]即选择状态为S、且末位字符为c时是否可行（bool） //因为单词之和首尾有关，所以转移的时候可以巧妙地用到a[last].r=a[i].l; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } char ss[519]; int n,f[(1<<17)][10],ans=0; struct node{ char l,r; int c; }a[22]; int id(char ch){ if(ch=='I') return 0; if(ch=='O') return 1; if(ch=='U') return 2; if(ch=='E') return 3; if(ch=='A') return 4; } int main(){ reads(n); for(int i=0;i<n;i++){ scanf("%s",ss); int len=strlen(ss); a[i].l=id(ss[0]),a[i].r=id(ss[len-1]),a[i].c=len; } for(int i=0;i<=(1<<n)-1;i++) for(int j=0;j<n;j++) if(i&(1<<j)) //枚举此时新加上的单词j，如果i状态包含这个单词 if(i==(1<<j)||f[i-(1<<j)][a[j].l]) //如果是状态中唯一单词||去掉它的情况出现过 f[i][a[j].r]=f[i-(1<<j)][a[j].l]+a[j].c,ans=max(ans,f[i][a[j].r]); printf("%d ",ans); return 0; //输出ans：接龙的最大长度 }
T8：【p3070】岛游记
- r*c的地图，有’S’:浅水(游泳),’X’:陆地(行走),’.’:深水三种地形。
- 刚开始在任意陆地上，陆地和浅水之间可以相互通行。但无论如何都不能走到深水。
- 要求把所有的岛屿(陆地的连通块)都经过一次。Q：最少要经过几个浅水区？
求所有‘X’所在连通块的编号：flag[i][j]，用num记录每个连通块的大小，进行spfa得出连通块之间的最短路。
然后dp：f[S][i] 即经过岛屿(连通块)的状态为S、最后岛屿为i时最少经过的浅水数。
- 方程：f[S][i]=min{f[S^i][k]+d[k,i]}。 // 其中 d[][] 记录两个连通块之间的最短路。
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } /*【p3070】岛游记 r*c的地图，有’S’:浅水(游泳),’X’:陆地(行走),’.’:深水三种地形。 刚开始在任意陆地上，陆地和浅水之间可以相互通行。但无论如何都不能走到深水。 要求把所有的岛屿(陆地的连通块)都经过一次。Q：最少要经过几个浅水区？ */ //求所有‘X’所在连通块的编号:flag[i][j]，用num记录每个连通块的大小，进行spfa得出连通块之间的最短路。 //然后dp：f[S][i]即经过岛屿(连通块)的状态为S、最后岛屿为i时最少经过的浅水数。 //方程：f[S][i]=min{f[S^i][k]+d[k,i]}。 //d[][]记录两个连通块之间的最短路 struct node{ int x,y; }maps[16][16]; //maps[][]记录每个连通块的每个格子 queue<node>q; //广搜队列，用于广搜确定连通块 和 SPFA int n,m,ans=1e9,tot=0,flag[59][59],num[59],d[59][59],dist[59][59]; char ss[59][59]; bool vis[59][59]; int f[(1<<16)][16]; const int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; bool in_(int x,int y){ return x>=1&&x<=n&&y>=1&&y<=m; } void bfs(int sx,int sy){ //记录第一个连通块的位置 node now1; now1.x=sx,now1.y=sy,q.push(now1); vis[sx][sy]=1,flag[sx][sy]=tot,num[tot]++; maps[tot][num[tot]]=now1; while(!q.empty()){ node now=q.front(),now1;q.pop(); for(int i=0;i<4;i++){ int xx=now.x+dx[i],yy=now.y+dy[i]; if(!in_(xx,yy)||vis[xx][yy]||ss[xx][yy]!='X') continue; now1.x=xx,now1.y=yy,q.push(now1),vis[xx][yy]=1,flag[xx][yy]=tot; num[tot]++,maps[tot][num[tot]]=now1; //进队并记录信息 } } } void spfa(int s){ //以连通块s作为起点 memset(vis,0,sizeof(vis)); memset(dist,127/3,sizeof(dist)); for(int i=1;i<=num[s];i++){ //属于该连通块的所有点 vis[maps[s][i].x][maps[s][i].y]=1; dist[maps[s][i].x][maps[s][i].y]=0,q.push(maps[s][i]); } node now,now1; //便于取出队列中的当前点 while(!q.empty()){ //进行SPFA now=q.front(),q.pop(),vis[now.x][now.y]=0; for(int i=0;i<4;i++){ int xx=now.x+dx[i],yy=now.y+dy[i]; if(!in_(xx,yy)||ss[xx][yy]=='.')continue; if(ss[xx][yy]=='X'){ //↓↓到达一个新的岛屿(连通块) if(dist[xx][yy]>dist[now.x][now.y]){ dist[xx][yy]=dist[now.x][now.y]; if(!vis[xx][yy]) vis[xx][yy]=1,now1.x=xx,now1.y=yy,q.push(now1); } d[flag[xx][yy]][s]=d[s][flag[xx][yy]]= //更新连通块间的最短路 min(d[s][flag[xx][yy]],min(d[flag[xx][yy]][s],dist[xx][yy])); } if(ss[xx][yy]=='S'){ //↓↓到达浅水区 if(dist[xx][yy]>dist[now.x][now.y]+1){ dist[xx][yy]=dist[now.x][now.y]+1; //更新点间最短路 if(!vis[xx][yy]) vis[xx][yy]=1,now1.x=xx,now1.y=yy,q.push(now1); } } } } } void DP(){ //状压dp memset(f,127/3,sizeof(f)); for(int i=1;i<=tot;i++) f[1<<(i-1)][i]=0; //初始化每个连通块 for(int S=1;S<=(1<<tot)-1;S++){ for(int i=1;i<=tot;i++){ //枚举当前状态能经过的最后节点 if(!(S&(1<<(i-1)))) continue; for(int j=1;j<=tot;j++){ //枚举上次经过的最后节点 if(j==i||!(S&(1<<(j-1)))) continue; f[S][i]=min(f[S][i],f[S^(1<<(i-1))][j]+d[j][i]); } } } } int main(){ reads(n),reads(m); for(int i=1;i<=n;i++) scanf("%s",ss[i]+1); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) //↓↓遍历整个连通块 if(!vis[i][j]&&ss[i][j]=='X') tot++,bfs(i,j); memset(d,63,sizeof(d)); //d[][]记录两个连通块之间的最短路 for(int i=1;i<=tot;i++) d[i][i]=0,spfa(i); //寻找两两连通块间的最短路 DP(); for(int j=1;j<=tot;j++) ans=min(ans,f[(1<<tot)-1][j]); cout<<ans<<endl; return 0; //↑↑枚举终点，得到最优解 }
T9：【p2915】奶牛混合起来
- 给出n个编号，问排序成混乱的队伍（相邻牛编号均超过k）的方案数。
状压dp。f[s][j] 表示：当前状态s，当前末尾为j的方案数。转移累加即可。
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } /*【p2915】奶牛混合起来 给出n个编号，问排序成混乱的队伍（相邻牛编号均超过k）的方案数。*/ int a[20]; ll f[(1<<16)][20]; //f[s][j]即：当前状态s，当前末尾为j的方案数 int main(){ int n,k; reads(n),reads(k); for(int i=1;i<=n;i++) reads(a[i]); for(int i=1;i<=n;i++) f[1<<(i-1)][i]=1; for(int s=0;s<=(1<<n)-1;s++) for(int i=1;i<=n;i++) if(s&(1<<(i-1))) for(int j=1;j<=n;j++) //if(i!=j&&(s&(1<<(j-1)))) if(abs(a[i]-a[j])>k) f[s][i]+=f[s^(1<<(i-1))][j]; ll ans=0; for(int i=1;i<=n;i++) ans+=f[(1<<n)-1][i]; printf("%lld ",ans); return 0; }
状压DPの简单变形
T10：【p2622】关灯问题
- n盏灯，m个按钮。每个按钮可以同时控制这n盏灯。
- 初始全开，给出不同开关的控制效果，最少按几次按钮才能全关？
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } /*【p2622】关灯问题 // 状压 + 广搜 n盏灯，m个按钮。每个按钮可以同时控制这n盏灯。 现在这些灯都是开的，给出所有开关对所有灯的控制效果， 问最少要按几下按钮才能全部关掉。*/ int n,m,a[109][1019]; bool vis[1000019]; struct node{ int s,step; }; // s：当前状态，step：所需min步数 int spfa(){ queue<node> q; vis[(1<<n)-1]=true; q.push( (node) {(1<<n)-1,0} ); //以全开为初始状态 while(!q.empty()){ node u=q.front(); q.pop(); if(u.s==0) return u.step; //若状态为0(全关)，返回当前步数 for(int i=1;i<=m;i++){ int ss=u.s; //选择一种操作，进行修改，将新状态入队 for(int j=1;j<=n;j++){ //遍历所有灯，按不同操作进行修改 if( a[i][j]==1 && (ss&(1<<j-1)) ) ss^=(1<<j-1); if( a[i][j]==-1 && !(ss&(1<<j-1)) ) ss|=(1<<j-1); } if(!vis[ss]) q.push((node){ss,u.step+1}),vis[ss]=true; } } return -1; //若遍历完所有状态都没有0，则输出-1 } int main(){ reads(n),reads(m); //灯数n，操作种数m for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) reads(a[i][j]); cout<<spfa()<<endl; return 0; } //bfs求达到目标状态的min次数
T11：【p1171】售货员的难题
- 从1号村庄去所有村庄再回来，选一条路线使总路程最短。
- f[s][j]：当前节点状态为s，到达j点的最短路径。
保证每条路线一定要经过1号村庄，所以枚举状态时每次要 s+=2 。
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } /*【p1171】售货员的难题 //限定性的状压dp 从1号村庄去所有村庄再回来，选一条路线使总路程最短。*/ // f[s][j]：当前节点状态为s，到达j点的最短路径。 //保证每条路线一定要经过1号村庄，所以枚举状态时每次要 s+=2 。 int ans=2e9,g[22][22],f[(1<<20)][22]; int main(){ int n; reads(n); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) reads(g[i][j]); memset(f,0x3f,sizeof(f)); f[1][1]=0; for(int s=1;s<=(1<<n)-1;s+=2) //保证状态中包含节点1 for(int i=1;i<=n;i++) if(f[s][i]<(int)3e5) //剪枝 for(int j=1;j<=n;j++) if(!(s&(1<<(j-1)))) //[注意]括号一定要打全 f[s|(1<<(j-1))][j]=min(f[s|(1<<(j-1))][j],f[s][i]+g[i][j]); for(int i=1;i<=n;i++) ans=min(ans,f[(1<<n)-1][i]+g[i][1]); cout<<ans<<endl; return 0; }
T12：【p3694】邦邦的合唱团
- N个偶像排成一列，来自M个不同的乐队。
- 要求让部分偶像出队，再站回自己应该站的位置。
- 注意：站回的位置一定是原来有人站、
- 而现在为空的位置。最少让多少偶像出列？
预处理前缀和：sum[i][j]即第i个乐队，在位置j前方，有多少人。
求区间的团队i人数直接可以用sum[i][r]-sum[i][l-1];
注意：每次放置一个团，一定会占据'p~p+num[i]（i团队人数）-1'的位置。
按照选择集合的顺序把每个团顺着放（很重要的思想），这样不会有遗漏。
- f[s]=min(f[s],f[s^(1<<i)]+num[i]-sum[i][p+num[i]-1]+sum[i][p-1]);
表示把第i个乐队放在p~(p+num[i]-1)，达到状态s，需要增加的最小代价。
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<algorithm> #include<cmath> #include<set> #include<vector> #include<map> #include<queue> using namespace std; typedef long long ll; void reads(int &x){ int fx=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} x=x*fx; //正负号 } /*【p3694】邦邦的合唱团 // 状压 + 前缀和 N个偶像排成一列，来自M个不同的乐队。要求让部分偶像出队，再站回自己应该站的位置。 注意：站回的位置一定是原来有人站、而现在为空的位置。最少让多少偶像出列？*/ //预处理前缀和：sum[i][j]即第i个乐队，在位置j前方，有多少人。 //求区间的团队i人数直接可以用sum[i][r]-sum[i][l-1]; //注意：每次放置一个团，一定会占据'p~p+num[i]（i团队人数）-1'的位置。 //按照选择集合的顺序把每个团顺着放（很重要的思想），这样不会有遗漏。 int f[(1<<22)]; int n,m,a[100019],num[22],sum[22][100019]; //f[s]=min(f[s],f[s^(1<<i)]+num[i]-sum[i][p+num[i]-1]+sum[i][p-1]); //↑↑表示把第i个乐队放在p~(p+num[i]-1)，达到状态s，需要增加的最小代价。 int main(){ reads(n),reads(m); for(int i=1;i<=n;i++){ reads(a[i]),num[a[i]]++; for(int j=1;j<=m;j++) sum[j][i]=sum[j][i-1]; sum[a[i]][i]++; } for(int s=0;s<(1<<m);s++) f[s]=(int)2e9; f[0]=0; //注意初始化&设置起点 for(int s=0;s<(1<<m);s++){ //每种状态（状态中所有数都放在前面 且 放完了） int p=1; for(int i=1;i<=m;i++) if(s&(1<<(i-1))) p+=num[i]; //顺序放置 for(int i=1;i<=m;i++) if((s&(1<<(i-1)))==0) //注意状压中的位数对应 f[s|(1<<(i-1))]=min(f[s|(1<<(i-1))],f[s]+num[i]-sum[i][p+num[i]-1]+sum[i][p-1]); } cout<<f[(1<<m)-1]<<endl; return 0; //注意：(s&(1<<(i-1)))==0这个地方，括号不能打掉 }
T13：【p3160】局部最小值
- n*m的棋盘。局部极小值：数值比所有相邻格子（八连通）都小。
- 给出所有局部极小值的位置，判断有多少个可能的矩阵。
f[i][j] 表示 填入前 i 个数，局部最小值的填入情况为 j 的方案数。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> #include<cmath> #include<map> using namespace std; typedef long long ll; /*【p3160】局部最小值 // 状压dp + bfs + 特判 n*m的棋盘。局部极小值：数值比所有相邻格子（八连通）都小。 给出所有局部极小值的位置，判断有多少个可能的矩阵。*/ //【分析】f[i][j] 表示 填入前 i 个数，局部最小值的填入情况为 j 的方案数。 void reads(int &x){ //读入优化（正负整数） int fx=1;x=0;char s=getchar(); while(s<'0'||s>'9'){if(s=='-')fx=-1;s=getchar();} while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+s-'0';s=getchar();} x*=fx; //正负号 } const int dx[9]={0,1,1,1,0,-1,-1,-1,0}; const int dy[9]={0,1,0,-1,-1,-1,0,1,1},mod=12345678; char ss[59]; int n,m,px[59],py[59],p,vis[10][10],min_[10][10],v[519],f[59][519]; int solve(){ memset(v,0,sizeof(v)); for(int i=0;i<(1<<p);i++){ //v[i]：每种集合状态i下的可填格子数目 memset(vis,0,sizeof(vis)); for(int j=0;j<p;j++) if(!(i&(1<<j))) for(int k=0;k<9;k++) vis[px[j]+dx[k]][py[j]+dy[k]]=1; for(int j=1;j<=n;j++) for(int k=1;k<=m;k++) v[i]+=!vis[j][k]; } memset(f,0,sizeof(f)); f[0][0]=1; for(int i=1;i<=n*m;i++) for(int j=0;j<(1<<p);j++){ if(v[j]>=i) f[i][j]=f[i-1][j]*(v[j]-i+1)%mod; for(int k=0;k<p;k++) if(j&(1<<k)) f[i][j]=(f[i][j]+f[i-1][j^(1<<k)])%mod; } return f[n*m][(1<<p)-1]; } int dfs(int x,int y){ if(y>m) x++,y=1; if(x>n) return solve(); //注意dfs的位置转化 //求满足‘给出的位置是局部最小值’总方案数 int i,ans=dfs(x,y+1); //深搜求此位置的总方案 //因为必须满足要‘非给出的位置不是局部最小值’，所以需要容斥， //即：总方案数-此点(x,y)为‘非给出的局部最小值’的方案数。 for(i=0;i<9;i++) if(min_[x+dx[i]][y+dy[i]]) break; //找出‘局部最小值’的点 //↓↓自己和八方向都不是局部最小值，填入之后就一定会变成局部最小值，与题目矛盾 if(i==9){ px[p]=x,py[p++]=y,min_[x][y]=1; //↓↓利用‘容斥原理’减掉 ans=(ans-dfs(x,y+1)+mod)%mod,p--,min_[x][y]=0; } return ans; } int main(){ reads(n),reads(m); for(int i=1;i<=n;i++){ scanf("%s",ss+1); for(int j=1;j<=m;j++) if(ss[j]=='X') px[p]=i,py[p++]=j; //局部最小值的点 } for(int i=0;i<p;i++){ //状压一般用0开始，所以p也从0开始 for(int j=0;j<i;j++) //【特判】局部最小值冲突的情况 if(abs(px[i]-px[j])<=1&&abs(py[i]-py[j])<=1) { puts("0"); return 0; } //不满足‘最小’的性质 min_[px[i]][py[i]]=1; //将局部最小值的点标记为1 } printf("%d ",dfs(1,1)); return 0; }
T14：【p3736】字符合并
- 每次将长度为n的01串中相邻的k个字符合并，得到新字符并获得分数。
- 得到的新字符和分数由这k个字符确定。你需要求出你能获得的最大分数。
- 输入ci和wi，ci表示长度为k的01串连成二进制后、
- 按从小到大顺序得到的第i种合并方案得到的新字符,
- wi表示第i种方案对应获得的分数。
用 f[i][j][s] 表示‘从i到j之间进行替换后成为s的状态’所能得到的最大值。
第一层循环枚举区间长度，用小区间维护大区间，第二层枚举左端点，第三层枚举中间值。
由于还有状压，第四层就是枚举状态了，由于我们每次合并都是以k为长度，右端点已经确定。
如果len=k-1，说明该串可以被合并，就去找每个合法状态中转化为0或1中最大的两个。
#pragma GCC optimize(2) #include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <queue> #include <stack> using namespace std; typedef long long ll; typedef unsigned long long ull; /*【p3736】字符合并 // 区间dp + 状压dp 每次将长度为n的01串中相邻的k个字符合并，得到新字符并获得分数。 得到的新字符和分数由这k个字符确定。你需要求出你能获得的最大分数。 输入ci和wi，ci表示长度为k的01串连成二进制后、 按从小到大顺序得到的第i种合并方案得到的新字符, wi表示第i种方案对应获得的分数。*/ /*【分析】f[i][j][s]表示‘从i到j之间进行替换后成为s的状态’所能得到的最大值。 第一层循环枚举区间长度，用小区间维护大区间，第二层枚举左端点，第三层枚举中间值。 由于还有状压，第四层就是枚举状态了，由于我们每次合并都是以k为长度，右端点已经确定。 如果len=k-1，说明该串可以被合并，就去找每个合法状态中转化为0或1中最大的两个。*/ int n,k,b[1<<8]; ll c[1<<8],f[301][301][1<<7]; char ss[301]; const ll inf=-1e9; int main(){ scanf("%d%d%s",&n,&k,ss+1); memset(f,-0x3f,sizeof(f)); for(int i=1;i<=n;i++) f[i][i][ss[i]-'0']=0; for(int s=0;s<(1<<k);s++) scanf("%d%lld",&b[s],&c[s]); for(int l=2;l<=n;l++) //【1】枚举dp区间长度 for(int i=1;i<=n-l+1;i++){ //【2】枚举dp区间左端点 int j=i+l-1,len=j-i; //dp区间右端点j while(len>k-1) len-=k-1; //此dp区间需要合并的次数 for(int t=j;t>0;t-=k-1) //挨个合并（倒序） for(int s=0;s<(1<<len);s++){ //新状态由小区间扩展而来 if(f[i][t-1][s]>inf&&f[t][j][0]>inf) f[i][j][s<<1]=max(f[i][j][s<<1],f[i][t-1][s]+f[t][j][0]); if(f[i][t-1][s]>inf&&f[t][j][1]>inf) f[i][j][s<<1|1]=max(f[i][j][s<<1|1],f[i][t-1][s]+f[t][j][1]); } if(len==k-1){ ll g[2]; g[0]=g[1]=inf;//过渡值g[0/1] for(int s=0;s<(1<<k);s++) if(f[i][j][s]>inf) g[b[s]]=max(g[b[s]],f[i][j][s]+c[s]); f[i][j][1]=g[1],f[i][j][0]=g[0]; } } ll ans=inf; for(int i=0;i<(1<<k);i++) ans=max(ans,f[1][n][i]); printf("%lld ",ans); }
一开始真心不知道为什么wa...（调了好久...）好吧发现是输入的锅...
T15：【p4163】排列
- 给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。
#pragma GCC optimize(2) #include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <queue> #include <stack> using namespace std; typedef long long ll; typedef unsigned long long ull; /*【p4163】排列 给一个数字串s和正整数d, 统计s有多少种不同的排列能被d整除（可以有前导0）。*/ // https://www.luogu.org/blog/MonsterQ/solution-p4163 int T,d,a[11],cnt,dp[1<<11][1001]; bool vis[11]; char ss[11]; int main(){ scanf("%d",&T); int len; while(T--){ memset(dp,0,sizeof(dp)); scanf("%s%d",ss+1,&d); len=strlen(ss+1),cnt=0; for(int i=1;i<=len;i++) a[i]=ss[i]-'0'; dp[0][0]=1; //dp赋初值 for(int S=0;S<(1<<len)-1;S++){ //S表示当前所选的状态集合 memset(vis,0,sizeof(vis)); //注意清零 for(int j=1;j<=len;j++) if(!(S&(1<<(j-1)))&&!vis[a[j]]){ //如果a[j]已经转移过就不能继续转移了,j表示遍历s中的各位数字 vis[a[j]]=1; for(int k=0;k<d;k++) //k表示此数对d取余后的数 dp[S|(1<<(j-1))][(k*10+a[j])%d]+=dp[S][k]; } } printf("%d ",dp[(1<<len)-1][0]); } }
T16：【p4363】一双木棋
#pragma GCC optimize(2) #include <cmath> #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <algorithm> #include <queue> #include <stack> using namespace std; typedef long long ll; typedef unsigned long long ull; /*【p4363】一双木棋 */ /*【分析】把每个格子的价值记成aij+bij。初始a,b二人得分为sum_ai,sum_bi。 如果i,j被a选了，sum_b中包含的bij抵消，此格子的相关得分变成两倍aij。最后差值/2即可。 所以每一步都选择此步能走的(aij+bij)max的？ //肯定是错的.. */ //艰难的30分（特判的30分...） /*【正解】单调递增的矩阵取数：轮廓线 + 状压 + 记忆化搜索 先放置m个0，再向其中插入n个1，1代表行，每个1右边有几个0就代表了这行选了几个数。 可参考 https://anoxiacxy.blog.luogu.org/solution-p4363 。*/ void reads(int &x){ int fx_=1;x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')fx_=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} } int n,m,a[11][11],b[11][11],ans=0,vis[(1<<22)],f[(1<<22)]; int dfs(int s,int op){ if(vis[s]) return f[s]; int tmp=op?-2e9:2e9; vis[s]=1; for(int i=0,j=n+1,k=1;i<n+m;i++){ if((s|(1<<i))!=s) k++; else j--; if(i==n+m-1||((s>>i)&3)!=1) continue; int s_=(s^(3<<i)); //翻转一个‘01’或‘10’ if(op) tmp=max(tmp,dfs(s_,op^1)+a[j][k]); else tmp=min(tmp,dfs(s_,op^1)-b[j][k]); } return f[s]=tmp; //因为有后效性，所以不能dp，必须要搜索 } int main(){ reads(n),reads(m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) reads(a[i][j]); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) reads(b[i][j]); f[((1<<n)-1)<<m]=0; vis[((1<<n)-1)<<m]=1; //↑↑轮廓线为长度为n+m的01串，初始为11...100...0 printf("%d ",dfs((1<<n)-1,1)); return 0; //进行dfs }
——时间划过风的轨迹，那个少年，还在等你