炮兵阵地同样离散化优化
内存400KB,运行时间61ms
#include<iostream>
#include<vector>
#define int long long
using namespace std;
const int N=1<<10;
int n,k;
vector<int> state;
vector<int> head[200];
vector<int> cnt;
int f[3][200][100];
bool check(int t){
for(int i=0;i<n;i++){
if((t>>i&1)&&(t>>i+1&1))
return false;
}
return true;
}
int count(int t){
int ans=0;
for(int i=0;i<n;i++){
if(t>>i&1) ans++;
}
return ans;
}
signed main(){
cin>>n>>k;
for(int i=0;i<1<<n;i++){
if(check(i)) {
state.push_back(i);
cnt.push_back(count(i));
}
}
for(int i=0;i<state.size();i++){
for(int j=0;j<state.size();j++){
int a=state[i],b=state[j];
if(((a&b)==0)&&(check(a|b))){
head[i].push_back(j);
}
}
}
f[0][0][0]=1;
//可以观察到,状态0是一个合法状态,并且肯定是第一个被加入state数组的
//也就是state=0这个状态对应的下标肯定是0
//所以我们这里就可以利用这一个性质,对f[0][0][0]取1
for(int i=1;i<=n;i++){
for(int a=0;a<state.size();a++){
for(int j=0;j<=k;j++){
f[i&1][a][j]=0;
for(int b:head[a]){
if(j<cnt[a])
continue;
f[i&1][a][j]+=f[(i-1)&1][b][j-cnt[a]];
}
}
}
}
int ans=0;
for(int i=0;i<state.size();i++){
ans+=f[n&1][i][k];
}
cout<<ans<<endl;
}