COJ 0260 HDNOIP201204四个国王

HDNOIP201204四个国王

难度级别：A； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B

试题描述

在N*M的棋盘上摆国际象棋中的“国王”。如果两个“国王”占据的格子有公共边或者公共顶点，那么他们就会相互攻击。现在想知道，一共有多少种不同的方法摆上K个互不攻击的国王呢？

输入

第一行包含三个整数，分别表示N、M和K。

输出

输出一个整数，表示方法数。若超过2147483647，你只用输出2147483648即可。

输入示例

样例输入1 3 3 4 样例输入2 5 100 50

输出示例

样例输出1 1 样例输出2 2147483648

其他说明

第一个样例只有一种可能： XOX OOO XOX X表示一个国王，O表示一个空格子。 第二个样例的方法数显然多于2147483647。 对70%的数据，N<=5，M<=5，0<=K<=4， 对另外30%的数据，N<=5，M<=100，0<=K<=N*M

题解：妈妈呀好题！

"n小思状压，网格用层次"，所以很容易得出DP：f[i][j][k]表示前i列放j个国王且第i列状态为a[k]的放法总数

转移：f[i][j][k]=sum(f[i-1][j-b[s_now]][s_think]) (j∈ok_set)

那么肿么求ok_set呢？暴力init就行，如果追求完美可以打表哦~

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 #define PAU putchar(' ')

 #define ENT putchar('\n')

 using namespace std;

 const int maxn=+,maxm=+,maxs=,maxt=,inf=-1u>>;

 long long f[maxn][maxm][maxs],sum;

 int a[maxt]={,,,,,,,,,,,,},b[maxt]={,,,,,,,,,,,,},p[]={,,,,,};

 int w[]={,,,,},c,n,m,k;bool g[maxt][maxt];

 inline int read(){

     int x=,sig=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')sig=-;ch=getchar();}

     while(isdigit(ch))x=*x+ch-'',ch=getchar();

     return x*=sig;

 }

 inline void write(int x){

     if(x==){putchar('');return;}if(x<)putchar('-'),x=-x;

     int len=,buf[];while(x)buf[len++]=x%,x/=;

     for(int i=len-;i>=;i--)putchar(buf[i]+'');return;

 }

 void init(){

     n=read();m=read();k=read();

       if(!k||n<=||m<=){write();return;}

       for(int i=;i<p[n]-;i++)

         for(int j=i+;j<p[n];j++){

             if(a[i]&a[j]) continue;

             int d;for(d=;d<;d++)if(w[d]&a[i]){

                   if(d<&&(w[d+]&a[j]))break;

                   if(d>&&(w[d-]&a[j]))break;

                 }if(d>)g[i][j]=g[j][i]=true;

             }g[][]=true;

       for(int i=;i<p[n];i++)f[][b[i]][i]=(b[i]<=k);

     return;

 }

 void work(){

     for(int i=;i<=m;i++)

         for(int j=;j<=k;j++)

               for(int c=;c<p[n];c++)

                 for(int d=;d<p[n];d++)if(g[c][d]&&j>=b[c])

                     f[i][j][c]+=f[i-][j-b[c]][d];

     return;

 }

 void print(){

     for(int j=;j<p[n];j++){

         sum+=f[m][k][j];

         if(sum>inf){puts("");return;}

     }write(sum);

     return;

 }

 int main(){init();work();print();return ;}