【BZOJ1087】【SCOI2005】互不侵犯King

一道简单的状压dp

话说我的状压dp居然是从插头dp学起的。。太可怕了

还是多做水题压压惊

考虑每行的可行方案只与上一行有关

那么先将所有单行内无冲突的方案找出来，以及两行之间无冲突可转移的方案，然后dp就是了

// <1087.cpp> - 05/27/16 15:02:32
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=550;
const int INF=1e9;
#define lowbit(x) x&-x
lol dp[10][100][MAXN];
int cnt[MAXN];
bool f1[MAXN],f[MAXN][MAXN];
int main(){
    int n=gi(),k=gi(),all=(1<<n)-1;
    for(int i=0;i<=all;i++)
        if(!(i&(i>>1))){
            f1[i]=1;
            for(int now=i;now;now-=lowbit(now))cnt[i]++;
            dp[1][cnt[i]][i]=1;
        }
    for(int i=0;i<=all;i++){
        if(!f1[i])continue;
        for(int j=0;j<=all;j++){
            if(!f1[j]||i&j||(i>>1)&j||i&(j>>1))continue;
            f[i][j]=1;
        }
    }
    for(int h=2;h<=n;h++)
        for(int i=0;i<=all;i++){
            if(!f1[i])continue;
            for(int j=0;j<=all;j++){
                if(!f[i][j])continue;
                for(int s=cnt[j];s<=k;s++)dp[h][s][j]+=dp[h-1][s-cnt[j]][i];
            }
        }
    lol ans=0;
    for(int i=0;i<=all;i++)ans+=dp[n][k][i];
    printf("%lld",ans);
    return 0;
}

// <1087.cpp> - 05/27/16 15:02:32

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=550;

const int INF=1e9;

#define lowbit(x) x&-x

lol dp[10][100][MAXN];

int cnt[MAXN];

bool f1[MAXN],f[MAXN][MAXN];

int main(){

int n=gi(),k=gi(),all=(1<<n)-1;

for(int i=0;i<=all;i++)

if(!(i&(i>>1))){

f1[i]=1;

for(int now=i;now;now-=lowbit(now))cnt[i]++;

dp[1][cnt[i]][i]=1;

}

for(int i=0;i<=all;i++){

if(!f1[i])continue;

for(int j=0;j<=all;j++){

if(!f1[j]||i&j||(i>>1)&j||i&(j>>1))continue;

f[i][j]=1;

}

for(int h=2;h<=n;h++)

for(int i=0;i<=all;i++){

if(!f1[i])continue;

for(int j=0;j<=all;j++){

if(!f[i][j])continue;

for(int s=cnt[j];s<=k;s++)dp[h][s][j]+=dp[h-1][s-cnt[j]][i];

}

lol ans=0;

for(int i=0;i<=all;i++)ans+=dp[n][k][i];

printf("%lld",ans);

return 0;

}