自动搬运

查看原文

来自洛谷，原作者为

	maruize :)

搬运于2025-08-24 21:55:24，当前版本为作者最后更新于2021-02-03 19:43:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

不太好写的状压DP

还是比较好想的：

• 把村庄以六进制压进状态。

• $f_{i,j,st}$前$i$步村庄状态为$j$仓库状态为$st$的最大人气,分三种情况转移。[code中的(1)-(3)]

注意:

• 合成是会触发多次的,需要写个循环。

$\color{brown}{code}$~

#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)$