题解 P3999 【[SHOI2013]二重镇】
maruize
·
·
题解
不太好写的状压DP
还是比较好想的：
注意:
```cpp
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<assert.h>
using namespace std;
typedef long long LL;
#define NS 47000//6^6
char opt[105];
int f[105][NS][6];//f[i][j][st]前i步村庄状态为j仓库状态为st的最大人气
int six[10];//6^k
inline int bit(register int n,register int b)
{return n/six[b]%6;}//n的6进制第b位(编号from0)
int val[NS]//==-1:invalid|==0不能消|other:消除获得的人气
,to[NS];//消除后不包括新产生的那个的其他的状态
void Up(int&a,int b){a=max(a,b);}//Update
int n;
void print6(int e){//六进制输出(debug)
char ou[10];int i;
memset(ou,'0',sizeof(ou));
for(i=0;e>0;i++,e/=6)
ou[i]=e%6+'0';
for(int j=n-1;j>=0;j--)putchar(ou[j]);
putchar(' ');
}
int main(){
int d;
scanf("%d%d",&n,&d);
scanf("%s",opt+1);
for(int i=1;i<=d;i++)opt[i]-='0';
six[0]=1;
for(int i=1;i<=n;i++)six[i]=six[i-1]*6;
for(int i=0;i<six[n];i++){
int cnt=0;
for(int j=0;j<n-1;j++){
int u=bit(i,j),k=2,s=0;
if(u==0||u!=bit(i,j+1))continue;
cnt++,s=u*six[j]+u*six[j+1],j++;
if(cnt>1){val[i]=-1;break;}
while(bit(i,j+1)==u)j++,k++,s+=u*six[j];
val[i]=k*(1<<u),to[i]=i-s;
}
if(cnt==0)val[i]=0,to[i]=i;//useless
}//预处理val,to
memset(f,-0x3f,sizeof(f)),f[0][0][0]=0;
for(int i=1;i<=d;i++){//i:第几步
for(int j=0;j<six[n];j++){//j:状态
if(val[j]!=0)continue;
Up(f[i][j][opt[i]],f[i-1][j][0]);//放仓库。(1)
for(int k=0;k<n;k++){//k:放哪儿
if(bit(j,k)!=0)continue;
for(int st=0;st<6;st++){//st:仓库
int nxt=j+six[k]*opt[i],v=0,t=1;
while(val[nxt]!=0){//循环"合成"
assert(val[nxt]!=-1);
v+=val[nxt];
nxt=to[nxt]+(opt[i]+t)%6*six[k];
//如果opt[i]+t==6那么val[nxt]肯定合法,所以只%一下就行可以少一行特判
t++;
}
Up(f[i][nxt][st],f[i-1][j][st]+v);//仓库不变。(2)
}
}
}
for(int j=0;j<six[n];j++){
if(val[j]!=0)continue;
for(int k=0;k<n;k++){
if(bit(j,k))continue;
for(int st=1;st<6;st++){//j,st:状态;k:放哪儿
int nxt=j+six[k]*st,v=0,t=1;
while(val[nxt]!=0){//循环同上
assert(val[nxt]!=-1);
v+=val[nxt];
nxt=to[nxt]+(st+t)%6*six[k];
t++;
}
Up(f[i][nxt][0],f[i][j][st]+v);//clear仓库。(3)
}
}
}
}
int ans=0;
for(int a=1;a<=d;a++)
for(int i=0;i<six[n];i++){
if(val[i]!=0)continue;
for(int st=0;st<6;st++)
ans=max(ans,f[a][i][st]);
}
printf("%d\n",ans);
return 0;
}
```
$O(6^{n+1}dn)