#include<iostream>
using namespace std;
int n,k;
int cnt[515];
long long f[10][100][515];
long long ans=0;
int main(){
	scanf("%d %d",&n,&k);
	for(int i=0;i<1<<n;i++)
	for(int j=1;j<=n;j++)
	if(i&(1<<j-1)) cnt[i]++;
	f[0][0][0]=1;
	for(int i=0;i<=n;i++)
	for(int j=0;j<=k;j++)
	for(int s=0;s<1<<n;s++){
		if(!f[i][j][s]) continue;
		for(int t=0;t<1<<n;t++){
			if(t&t<<1) continue;
			if(s&(t|t<<1|t>>1)) continue;
			if(j+cnt[t]>k) continue;
			f[i+1][j+cnt[t]][t]+=f[i][j][s];
		}
	}
	for(int i=0;i<1<<n;i++) ans+=f[n][k][i];
	printf("%lld",ans);
	return 0;
}

70分代码，RE了4个点，但写成这样就过了

#include<iostream>
using namespace std;
int n,k;
int cnt[515];
long long f[20][100][515];
long long ans=0;
int main(){
	scanf("%d %d",&n,&k);
	for(int i=0;i<1<<n;i++)
	for(int j=1;j<=n;j++)
	if(i&(1<<j-1)) cnt[i]++;
	f[0][0][0]=1;
	for(int i=0;i<=n;i++)
	for(int j=0;j<=k;j++)
	for(int s=0;s<1<<n;s++){
		if(!f[i][j][s]) continue;
		for(int t=0;t<1<<n;t++){
			if(t&t<<1) continue;
			if(s&(t|t<<1|t>>1)) continue;
			if(j+cnt[t]>k) continue;
			f[i+1][j+cnt[t]][t]+=f[i][j][s];
		}
	}
	for(int i=0;i<1<<n;i++) ans+=f[n][k][i];
	printf("%lld",ans);
	return 0;
}

是N大了吗？可是我f数组后面的状态没改也过了啊