-
状压dp。
想学的推荐别看我博客。
呃不得不学的，dp专题确实难搞QWQ。做完第一题再来总结一下吧。
P1896 [SCOI2005] 互不侵犯呃啊这一题！其实之前看过的，主要是这个状态压缩呀它要预处理。然后你要处理出所有的情况，就是行的情况你要处理出来才能枚举呀。#include#define int long long using namespace std; int n,m,k,f[11][200][200],cnt=0,num[10001],sum[10001],ans=0; //f[i][j][k]的状态表示在第i行j的状况下已经放了k个国王 (i一共放了k个) int getsum(int S) { int tot=0; while(S) tot+=(S&1),S>>=1; return tot; } void init() { cnt=0; for(int i=0;i<(1<<n);i++) { if(i&(i<<1)) continue ;//如果相邻的两个都放了就g num[++cnt]=i;sum[cnt]=getsum(i);//s是放的位置（每个国王），num是放的数量 //若是这个位置放下国王，统计一下 } return ; } void dp() { f[0][1][0]=1;//在第0行的一号状态放0个有一种情况。 for(int i=1;i<=n;i++) { for(int j=1;j<=cnt;j++) { for(int l=0;l<=k;l++)//枚举之前摆了的国王 (!!!我也摆！！！) { if(l<sum[j]) continue ; for(int t=1;t<=cnt;t++) { if((num[t] & num[j])||(num[t] & (num[j]<<1))||(num[t] & (num[j]>>1))) continue ; //看看是否与之前有冲突 f[i][j][l]+=f[i-1][t][l-sum[j]];//转移向前 } } } } return ; } signed main() { scanf("%lld%lld",&n,&k); init();dp();ans=0; for(int i=1;i<=cnt;i++) ans+=f[n][i][k];//printf("%lld %lld %lld\n",i,k,ans);//printf("%lld ",ans); printf("%lld",ans); return 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
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
P2704 [NOI2001] 炮兵阵地这题的转移状态会多很多，首先，我们压去前两行（欸这是一个小知识点），呃其他就可以直接转啦，问题在于细节很多，第一：
int getsum(int S) { int tot=0; while(S) tot+=(S&1),S>>=1; return tot; }- 1
- 2
- 3
- 4
- 5
- 6
for(int i=0;i<=mm;i++) { if((i&(i<<1))||(i&(i<<2))) continue ; num[++cnt]=i,sum[cnt]=getsum(i); if(a[1]&num[cnt]) ans=max(ans,sum[cnt]); }- 1
- 2
- 3
- 4
- 5
- 6
这个就会是我们以后将沿用的板子，压缩了空间以及计算好了完美情况。
第二：注意你要计算第一第二行的情况，就因为这个搞了半天。
第三：你tm是不是忘记把整一排不放的情况忘了！！！计数要从0开始啊铸币。
P1879 [USACO06NOV]Corn Fields G第三题。大概我好像是有些上手了吧，就没花多久，不过还有一个小问题就是初始化的时候搞了一会。#include#define int long long using namespace std; int n,m,a[1001],sum[10001],num[10001],cnt=0,mm,ans=0,mod=1e9; int f[20][6000]; int getsum(int x) { int tot; while(x) tot+=(x&1),x>>=1; return tot; } signed main() { scanf("%lld%lld",&n,&m);mm=(1<<m)-1; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int x;scanf("%lld",&x); if(x==0) a[i]|=(1<<(j-1));//?/a[i]|=(1< - 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
P2622 关灯问题II状压dp的好题，考虑如何转移，那么明显枚举状态而不是枚举方案。（可以先用一种方案再用前面用过的方案，那么枚举方案会出事），那么再考虑直接枚举按钮，然后转移就行啦
#includeusing namespace std; int n,m,a[101][101],f[10001],nn;//f[i]表示的是从最初全0状态转移到i的状态最少需要几次 //f[nn]是全开的 //在这一份代码中cnt是没有用的，因为其左右点没有任何的限制 int main() { memset(f,63,sizeof(f)); scanf("%d%d",&n,&m);nn=(1<<n)-1; for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); } f[nn]=0; for(int i=nn;i>=0;i--) { for(int j=1;j<=m;j++) { int now=i; for(int k=1;k<=n;k++) { if(a[j][k]==0) continue ; if(a[j][k]==1&&(i&(1<<(k-1)))) now^=(1<<(k-1)); if(a[j][k]==-1&&!(i&(1<<(k-1)))) now^=(1<<(k-1)); } f[now]=min(f[now],f[i]+1); } } if(f[0]==f[nn+1]) printf("-1"); else printf("%d",f[0]); return 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
P2396 yyy loves Maths VII说这题状压未免太过勉强，不过判断01的方式确实学到不少。
#include#define lowbit(x) x&(-x) using namespace std; int n,m,b1,b2,f[1<<24],dis[1<<24],nn,mod=1e9+7; main() { scanf("%d",&n);nn=(1<<n)-1; for(int i=0;i<=n-1;i++) scanf("%d",&dis[1<<i]); scanf("%d",&m); if(m==1) scanf("%d",&b1); if(m==2) scanf("%d%d",&b1,&b2); f[0]=1; for(int i=1;i<=nn;i++) { dis[i]=dis[i^lowbit(i)]+dis[lowbit(i)];//看看自己，是不是和b要匹配 if(dis[i]==b1||dis[i]==b2) continue; for(register int j = i, k = lowbit(j); j; j ^= k, k = lowbit(j)) { f[i] += f[i^k]; if(f[i] > mod) f[i] -= mod; } } printf("%d",f[nn]); return 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
P2473 [SCOI2008] 奖励关呃看看就懂啦，注意要从后往前算哦
#includeusing namespace std; int K,n,m,num[100001],nn; double f[101][1<<16],p[100001]; int main() { scanf("%d%d",&K,&n);nn=(1<<n)-1; for(int i=1;i<=n;i++) { scanf("%lf",&p[i]); int x;while(scanf("%d",&x),x!=0) num[i]|=(1<<(x-1)); } for(int i=K;i>=1;i--) { for(int j=0;j<=nn;j++) { for(int k=1;k<=n;k++) { if((j&num[k])==num[k]) f[i][j]+=max(f[i+1][j],f[i+1][j|(1<<(k-1))]+p[k]); else f[i][j]+=f[i+1][j]; } f[i][j]/=n; } } printf("%lf",f[1][0]); return 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
好啦最后一道，所有的也都是为了这一题Grouping,记录状态枚举子集，左右开弓。
//这题我们预处理出每一种组合 //然后枚举子集将自己拆成两。 #include#define int long long using namespace std; int n,m,f[1<<16],a[16][16],nn,val[1<<16]; main() { scanf("%lld",&n);nn=(1<<n)-1;//printf(" %d",nn); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%lld",&a[i][j]); } for(int i=1;i<=nn;i++) { for(int j=1;j<=n;j++) { for(int k=1;k<=j-1;k++) { if(((1<<(k-1))&i)&&((1<<(j-1))&i)) val[i]+=a[j][k]; } } // printf("%d\n",val[i]); } for(int i=1;i<=nn;i++) { f[i]=val[i]; for(int j=i&(i-1);j>=1;j=i&(j-1)) f[i]=max(f[i],f[i^j]+f[j]); } printf("%lld",f[nn]); return 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
补一题难一些的？P5005 中国象棋 - 摆上马，不过是高级些罢了。倒也没表面上那么难，只不过判断稍微麻烦些，作为一道练手的题目大抵也是不错的。不过！做到一半的我发现，有蹩马腿这一操作，那么复杂些了.
#include#define int long long using namespace std; int n,m,cnt=0,num[100001],sum[100001],nn,mod=1e9+7; int f[5][70][70],ans=0; //int getsum(int x) //{ // int tot=0; // while(x) tot+=(x&1),x>>=1; // return tot; //} main() { int Y;scanf("%lld%lld",&n,&Y);nn=(1<<Y)-1; if(n==1) { printf("%lld",(1<<Y)); return 0; } // for(int i=0;i<=nn;i++) num[cnt]=i;//sum[cnt]=getsum(i); int tmp=0; for(int i=2;i<=n;i++) { tmp^=1; for(int j=0;j<=nn;j++) { for(int k=0;k<=nn;k++) { f[tmp][j][k]=0; if(!(((j&(~(j>>1)))&(k>>2))||((j&(~(j<<1)))&(k<<2))||(((k&(~(k>>1)))&(j>>2)))||((k&(~(k<<1)))&(j<<2)))) { if(i==2) f[tmp][j][k]=1; else { for(int l=0;l<=nn;l++) { if(!(((j&(~k))&(l>>1))||((j&(~k))&(l<<1))||((l&(~k))&(j>>1))||((l&(~k))&(j<<1)))) { f[tmp][j][k]=(f[tmp][j][k]+f[tmp^1][k][l])%mod; } } } if(i==n) ans=(ans+f[tmp][j][k])%mod; } } } } printf("%lld",ans); return 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
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
呃有道km的题但是可以直接爆搜：P1559 运动员最佳匹配问题…不行听说爆搜被卡了但是！我们还可以尝试状压dp。
#include//#define int long long #define lowbit(x) x&(-x) using namespace std; int n,m,f[3][1<<20+1],p[202][202],q[202][202],num[1<<20+1]; int getsum(int x) { int tot=0; while(x) tot+=(x&1),x>>=1; return tot; } int main() { scanf("%d",&n);int nn=(1<<n)-1; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%d",&p[i][j]); } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) scanf("%d",&q[i][j]); } for(int i=1;i<n;i++) num[1<<i]=i; memset(f,0,sizeof(f));int tmp=0; for(int i=1;i<=n;i++) { tmp^=1; for(int j=0;j<=nn;j++) { if(getsum(j)!=i) continue ; int k=j; while(k) { int tt=lowbit(k); f[tmp][j]=max(f[tmp][j],f[tmp^1][j-tt]+p[i][num[tt]+1]*q[num[tt]+1][i]); k-=tt; } // printf("%d %d = %d\n",i,j,f[tmp][j]); } } printf("%d",f[tmp][nn]); return 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
- 42
- 43
-
相关阅读:
QT第三方库加载pro解读
c++调用windows vhd接口挂在vhd虚拟盘
Java基础-day05
回归测试：意义、挑战、最佳实践和工具
Flash存储芯片：NOR Flash、NAND Flash、UFS和eMMC的比较与解析
JAR防止反编译
10-集合3-Map
【实测】python模拟jenkins的定时设置时间库：------------------【 python_jenkins_monitor 】
【C++】类和对象——构造函数和析构函数
自然语言处理（NLP）—— Rasa中config.yml
- 原文地址：https://blog.csdn.net/cn_tigerhan/article/details/127794470
