南京百度seo排名,搜狗网站seo,网站优化成功案例,电脑维修网站模板下载一看数据范围#xff0c;如果是枚举所有的棋盘情况#xff0c;2^K#xff0c;肯定超了#xff0c;自然是要一行一行递推#xff0c;而相邻这个情况用位运算会比较方便#xff0c;所以用状压dp。 具体算法#xff1a;dp[i][j][k]表示第i行#xff0c;前i行有j个棋子如果是枚举所有的棋盘情况2^K肯定超了自然是要一行一行递推而相邻这个情况用位运算会比较方便所以用状压dp。 具体算法dp[i][j][k]表示第i行前i行有j个棋子第i行的棋子情况。第一行初始化一下符合条件的设为1.然后循环枚举出第i行m总数的棋子j的前一行状态k的这一行状态验证是否相邻是否总数超过。 AC代码
#includebits/stdc.h
using namespace std;
int N,K;
long long dp[100][100][110]{0};
int count(int x)
{int cnt0;while(x){int tx%2;if(t)cnt1;x/2;}return cnt;}
int main()
{cinNK;for(int i0;i1N;i){if(i(i1)||count(i)K)continue;dp[1][count(i)][i]1;}for(int i2;iN;i){for(int m0;mK;m){for(int j0;j(1N);j){for(int k0;k(1N);k) {if(j(j1)||k(k1)||j(k1)||(j1)(k)||(jk)||mcount(j)count(k))continue;dp[i][m][j]dp[i-1][m-count(j)][k];}}}}long long ans0;for(int i0;i1N;i){ansdp[N][K][i];}coutans;return 0;
}
