P1896 [SCOI2005]互不侵犯

30分 一直调不过

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>

#define ll long long

using namespace std;

ll f[10][1000][90];int s[10],rightt[1000],n,k;
ll ans;

int main() {
	scanf("%d%d",&n,&k);
	int MAX=1<<n;
	
	for(int i=0;i<MAX;i++) {
		for(int j=0;j<n;j++) {
			if((i>>j)&1) {
				++s[i];
				if(((i>>j)&3)==3) rightt[i]=1;
			}
		}
		f[0][i][s[i]]=!rightt[i];
	}
	
	for(int i=1;i<n;i++) {
		for(int x=0;x<MAX;x++) {
			if(rightt[x]) continue;
			for(int y=0;y<MAX;y++) {
				if(rightt[y]) continue;
				if((x&y)||((x>>1)&y)||(x&(y>>1))) continue;
				for(int t=0;t+s[x]<=k;t++) {
					f[i][x][t+s[x]]+=f[i-1][y][t];
				}
			}
		}
	}
	
	for(int i=0;i<MAX;i++) ans+=f[n-1][i][k];
	printf("%lld",ans);
}