P2704 [NOI2001] 炮兵阵地
2024年3月29日
code
#include<iostream>
using namespace std;
const long long MAXN=15;
long long n,k;
long long f[MAXN][MAXN*MAXN][1<<MAXN];
long long cnt[1<<MAXN];
long long can[1<<MAXN];
long long num;
int main(){
cin>>n>>k;
for(long long s=0;s<(1<<n);s++){
long long tot=0,s1=s;
while(s1){
if(s1&1)tot++;
s1>>=1;
}
cnt[s]=tot;
if((((s<<1)|(s>>1))&s)==0){
can[++num]=s;
}
}
f[0][0][0]=1;
for(long long i=1;i<=n;i++){
for(long long l=1;l<=num;l++){
long long s1=can[l];
for(long long r=1;r<=num;r++){
long long s2=can[r];
if(((s2|(s2<<1)|(s2>>1))&s1)==0){
for(long long j=0;j<=k;j++){
if(j-cnt[s1]>=0)f[i][j][s1]+=f[i-1][j-cnt[s1]][s2];
}
}
}
}
}
long long ans=0;
for(long long i=1;i<=num;i++){
ans+=f[n][k][can[i]];
}
cout<<ans<<"\n";
return 0;
}

要开 longlong!

继续阅读
所有文章
2024年3月29日

P1929阶梯之谜

©Mooncyan 2024