{"id":167,"date":"2010-03-20T12:52:00","date_gmt":"2010-03-20T04:52:00","guid":{"rendered":"http:\/\/localhost\/?p=167"},"modified":"2010-03-20T12:52:00","modified_gmt":"2010-03-20T04:52:00","slug":"scoi2005_nonaggression_king","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=167","title":{"rendered":"[SCOI2005]\u4e92\u4e0d\u4fb5\u72afKing"},"content":{"rendered":"\n

[SCOI2005]\u4e92\u4e0d\u4fb5\u72afKing <\/p>\n

Time Limit:10000MS  Memory Limit:165536K
Total Submit:13 Accepted:9
Case Time Limit:1000MS<\/p>\n

Description <\/strong><\/p>\n

\u5728N\u00d7N\u7684\u68cb\u76d8\u91cc\u9762\u653eK\u4e2a\u56fd\u738b\uff0c\u4f7f\u4ed6\u4eec\u4e92\u4e0d\u653b\u51fb\uff0c\u5171\u6709\u591a\u5c11\u79cd\u6446\u653e\u65b9\u6848\u3002\u56fd\u738b\u80fd\u653b\u51fb\u5230\u5b83\u4e0a\u4e0b\u5de6\u53f3\uff0c\u4ee5\u53ca\u5de6\u4e0a\u5de6\u4e0b\u53f3\u4e0a\u53f3\u4e0b\u516b\u4e2a\u65b9\u5411\u4e0a\u9644\u8fd1\u7684\u5404\u4e00\u4e2a\u683c\u5b50\uff0c\u51718\u4e2a \u683c\u5b50\u3002 <\/p>\n

Input <\/strong><\/p>\n

\u53ea\u6709\u4e00\u884c\uff0c\u5305\u542b\u4e24\u4e2a\u6570N\uff0cK \uff08 1 <=N <=9, 0 <= K <= N * N\uff09 <\/p>\n

Output <\/strong><\/p>\n

\u65b9\u6848\u6570\u3002 <\/p>\n

Sample Input <\/strong><\/p>\n

3 2<\/p>\n

Sample Output <\/strong><\/p>\n

16<\/p>\n

Source <\/strong><\/p>\n

\u4eca\u5929\u65e9\u4e0a\u6211\u4e00\u76f4\u5728\u88ab\u9898\u8650\u3002\u3002\u770b\u4e867\u30018\u9053\u6ca1\u4e00\u9053\u4f1a\u7684\uff0c\u6211\u771f\u662f\u592a\u83dc\u4e8655555
\u597d\u4e0d\u5bb9\u6613\u770b\u5230\u9053\u4f1a\u7684\u8fd8\u8fd9\u4e48\u6c34\u3002\u3002\u56e7\u6b7b\u4e86\u3002\u3002
61.187.179.132:8080\/JudgeOnline\/showproblem<\/a>
\u989d\u3002\u8fd9\u9053\u9898\u76ee\u9996\u5148dfs\u51fa\u6240\u6709\u53ef\u80fd\u7684\u72b6\u6001\uff08\u4e0d\u80fd\u6709\u8fde\u7eed\u76841\uff09\u3002\u3002\u7136\u540e\u9884\u5904\u7406\u51fa\u6240\u6709\u6570\u4e2d1\u7684\u4e2a\u6570\u3002\u7136\u540e\u76f4\u63a5DP\u5c31OK\u4e86\u3002\u3002
Code\uff1a
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=9,maxk=maxn*maxn;
typedef long long ll;
ll dp[2][maxk+1][1<<maxn]={0};
int state[1<<maxn],cnt=0,N,K,C[1<<maxn];
void dfs(int p,int s)
{
if(p==N){state[cnt++]=s;return;}
dfs(p+1,s*2);
if(!(s&1))dfs(p+1,s*2+1);
}
inline bool Legal(int a,int b)
{
a=state[a];b=state[b];
return !(a&b)&&!((a<<1)&b)&&!((a>>1)&b);
}
inline int Count(int a)
{
a=state[a];
return C[a];
}
int main()
{
\/\/freopen("in","r",stdin);
cin>>N>>K;
int now=0,old=1;
dp[now][0][0]=1;dfs(0,0);
C[0]=0;
for(int i=1;i<(1<<N);i++)
C[i]=C[i\/2]+(i&1);
rep(n,N)
{
swap(now,old);memset(dp[now],0,sizeof(dp[now]));
rep(k,K+1)rep(ps,cnt)rep(ns,cnt)
if(k-Count(ns)>=0&&Legal(ns,ps))
{
dp[now][k][ns]+=dp[old][k-Count(ns)];
}
}
ll ans=0;
rep(s,cnt) ans+=dp[now][K][s];
cout<<ans<<endl;
} <\/p>\n","protected":false},"excerpt":{"rendered":"

[SCOI2005]\u4e92\u4e0d\u4fb5\u72afKing Time Limit:10000MS  Memory Limit:165536KTotal Submit:13 Accepted:9 Case Time Limit:1000MS Description \u5728N\u00d7N\u7684\u68cb\u76d8\u91cc\u9762\u653eK\u4e2a\u56fd\u738b\uff0c\u4f7f\u4ed6\u4eec\u4e92\u4e0d\u653b\u51fb\uff0c\u5171\u6709\u591a\u5c11\u79cd\u6446\u653e\u65b9\u6848\u3002\u56fd\u738b\u80fd\u653b\u51fb\u5230\u5b83\u4e0a\u4e0b\u5de6\u53f3\uff0c\u4ee5\u53ca\u5de6\u4e0a\u5de6\u4e0b\u53f3\u4e0a\u53f3\u4e0b\u516b\u4e2a\u65b9\u5411\u4e0a\u9644\u8fd1\u7684\u5404\u4e00\u4e2a\u683c\u5b50\uff0c\u51718\u4e2a \u683c\u5b50\u3002 Input \u53ea\u6709\u4e00\u884c\uff0c\u5305\u542b\u4e24\u4e2a\u6570N\uff0cK \uff08 1 <=N <=9, 0 <= K <= N * N\uff09 Output \u65b9\u6848\u6570\u3002 Sample Input 3 2 Sample Output 16 Source \u4eca\u5929\u65e9\u4e0a\u6211\u4e00\u76f4\u5728\u88ab\u9898\u8650\u3002\u3002\u770b\u4e867\u30018\u9053\u6ca1\u4e00\u9053\u4f1a\u7684\uff0c\u6211\u771f\u662f\u592a\u83dc\u4e8655555\u597d\u4e0d\u5bb9\u6613\u770b\u5230\u9053\u4f1a\u7684\u8fd8\u8fd9\u4e48\u6c34\u3002\u3002\u56e7\u6b7b\u4e86\u3002\u300261.187.179.132:8080\/JudgeOnline\/showproblem\u989d\u3002\u8fd9\u9053\u9898\u76ee\u9996\u5148dfs\u51fa\u6240\u6709\u53ef\u80fd\u7684\u72b6\u6001\uff08\u4e0d\u80fd\u6709\u8fde\u7eed\u76841\uff09\u3002\u3002\u7136\u540e\u9884\u5904\u7406\u51fa\u6240\u6709\u6570\u4e2d1\u7684\u4e2a\u6570\u3002\u7136\u540e\u76f4\u63a5DP\u5c31OK\u4e86\u3002\u3002Code\uff1a#include<cstdio>#include<iostream>#include<algorithm>#include<string>#include<vector>#include<cstring>#define rep(i,n) for(int i=0;i<n;i++)#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=9,maxk=maxn*maxn;typedef long long ll;ll dp[2][maxk+1][1<<maxn]={0};int state[1<<maxn],cnt=0,N,K,C[1<<maxn];void dfs(int p,int s){ if(p==N){state[cnt++]=s;return;} […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/167"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=167"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/167\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=167"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=167"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=167"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}