状压 (dp)
1、[SDOI2009]Bill的挑战
(f[i][j]) 表示匹配到字符串的第 (i) 位状态为 (j) 的方案数
那么方程就很明显了，每次枚举第 (i) 位的字母 (alpha) 然后 (O(n)) 判断就好了
时间复杂度 (O(26Tlen2^nn))
(Code Below:)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int p=1e6+3;
int n,k,len,H[20],lg[1<<15],f[51][1<<15];
char s[16][51];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
int main()
{
register int T=read(),i,j,k,t,now,l,ans;
H[0]=1;
for(i=1;i<32768;i++) lg[i]=lg[i>>1]+(i&1);
for(i=1;i<20;i++) H[i]=H[i-1]<<1;
while(T--){
n=read(),k=read();
for(i=1;i<=n;i++) scanf("%s",s[i]+1);
if(n<k){
printf("0
");
continue;
}
len=strlen(s[1]+1);
memset(f,0,sizeof(f));
f[0][H[n]-1]=1;
for(i=1;i<=len;i++)
for(j=0;j<H[n];j++)
if(f[i-1][j]&&lg[j]>=k){
for(t=0;t<26;t++){
now=0;
for(l=1;l<=n;l++)
if((j&H[l-1])&&(s[l][i]=='?'||s[l][i]==t+'a')) now|=H[l-1];
f[i][now]=(f[i][now]+f[i-1][j])%p;
}
}
ans=0;
for(int i=0;i<H[n];i++)
if(lg[i]==k) ans=(ans+f[len][i])%p;
printf("%d
",ans);
}
return 0;
}
2、[SDOI2009]学校食堂
状压 (dp) 好题！
首先 (a or b - a and b = a xor b)
(f[i][j][k]) 表示到第 (i) 个人状态为 (j) 最后一个打饭的编号为 (i+k) 的方案数
那么就可以转移了
if(j&1) chkmin(f[i+1][j>>1][k+7],f[i][j][k+8]);
else {
int lim=inf;
for(int l=0;l<=7;l++){
if(!(j&(1<<l))){
if(i+l>lim) break;
chkmin(lim,i+l+B[i+l]);
chkmin(f[i][j|(1<<l)][l+8],f[i][j][k+8]+(i+k?T[i+k]^T[i+l]:0));
}
}
}
(Code Below:)
#include <bits/stdc++.h>
using namespace std;
const int maxn=1000+10;
const int inf=0x3f3f3f3f;
int n,T[maxn],B[maxn],f[maxn][1<<8][16];
inline int read(){
register int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return (f==1)?x:-x;
}
inline void chkmin(int &a,int b){a=a<b?a:b;}
int main()
{
int Case=read();
while(Case--){
n=read();
for(int i=1;i<=n;i++)
T[i]=read(),B[i]=read();
memset(f,inf,sizeof(f));
f[1][0][7]=0;
for(int i=1;i<=n;i++)
for(int j=0;j<256;j++)
for(int k=-8;k<=7;k++){
if(j&1) chkmin(f[i+1][j>>1][k+7],f[i][j][k+8]);
else {
int lim=inf;
for(int l=0;l<=7;l++){
if(!(j&(1<<l))){
if(i+l>lim) break;
chkmin(lim,i+l+B[i+l]);
chkmin(f[i][j|(1<<l)][l+8],f[i][j][k+8]+(i+k?T[i+k]^T[i+l]:0));
}
}
}
}
int ans=inf;
for(int i=0;i<=8;i++)
chkmin(ans,f[n+1][0][i]);
printf("%d
",ans);
}
return 0;
}
3、[CQOI2018]解锁屏幕
(check) 好麻烦啊
(Code Below):
#include <bits/stdc++.h>
#define res register int
using namespace std;
const int p=1e8+7;
int n,x[20],y[20],H[20],a[20][20],dp[1<<20][20],vis[1<<20][20],ans;
int head=1,tail=0,q[(1<<20)*20*2+10];
int check(int k,int f,int j){
if(k==f||k==j) return 0;
if(x[f]==x[k]||x[f]==x[j]){
if(x[f]==x[k]&&x[f]==x[j]&&(y[f]<=y[k])==(y[k]<=y[j])) return 1;
if(y[f]==y[k]&&y[f]==y[j]&&(x[f]<=x[k])==(x[k]<=x[j])) return 1;
return 0;
}
if((x[f]<=x[k])==(x[k]<=x[j])&&(y[f]<=y[k])==(y[k]<=y[j])&&(y[f]-y[k])*(x[f]-x[j])==(y[f]-y[j])*(x[f]-x[k])) return 1;
return 0;
}
void add(res &x,const res &y){
x=x+y<p?x+y:x+y-p;
}
int main()
{
scanf("%d",&n);
res i,j,f,st;H[0]=1;
for(i=1;i<=20;i++) H[i]=H[i-1]<<1;
for(i=0;i<n;i++) scanf("%d%d",&x[i],&y[i]);
for(f=0;f<n;f++)
for(j=0;j<n;j++){
if(f==j) continue;
for(i=0;i<n;i++) if(check(i,f,j)) a[f][j]+=1<<i;
}
for(i=0;i<n;i++) dp[H[i]][i]=vis[H[i]][i]=1,q[++tail]=H[i],q[++tail]=i;
while(head<=tail){
i=q[head++];f=q[head++];
st=__builtin_popcount(i);
if(st>=4) add(ans,dp[i][f]);
for(j=0;j<n;j++){
if(i&H[j]||!((a[f][j]&i)==a[f][j])) continue;
add(dp[i|H[j]][j],dp[i][f]);
if(!vis[i|H[j]][j]) vis[i|H[j]][j]=1,q[++tail]=i|H[j],q[++tail]=j;
}
}
printf("%d
",ans);
return 0;
}