Pieces Assignment
Source : zhouguyue | |||
Time limit : 1 sec | Memory limit : 64 M |
Submitted : 267, Accepted : 107
Background
有一个n*m的棋盘(n、m≤80,n*m≤80)要在棋盘上放k(k≤20)个棋子,使得任意两个棋子不相邻(每个棋子最多和周围4个棋子相邻)。求合法的方案总数。
Input
本题有多组测试数据,每组输入包含三个正整数n,m和k。
Output
对于每组输入,输出只有一个正整数,即合法的方案数。
Sample Input
2 2 3 4 4 1
Sample Output
0 16
思路:
状态 DP。以行为标准,因为 n * m <= 80,说明因为 8 * 8 = 81 > 80,所以行列不可能同时大于或者等于 8,行列至少有一个是小于8的,故考虑的时候始终让列数小于 8,故一行有无放棋子的可能是 2 ^ 8,因为不要求相邻,所以可以通过一组二进制来表示一行可能存在的棋子的情况。比如该棋盘大小为 4 X 3,那么说明一行可能出现的情况是 000 , 001 , 010 ,100 , 101 5 种情况。而每个二进制数都可以用一个十进制数来表示。用 s 数组记录每个可能情况的二进制所对应的十进制数,用 c 数组记录每个可能情况的二进制所对应的 1 的个数。预处理这些序列之后,就可以递推下去了。
用 dp [ i ] [ j ] [ k ],代表第 i 行时,运用 j 这个二进制的放置方法,所构成到这行为止总共的棋子数为 k 的情况总数。那么:
dp [ i ] [ j ] [ k ] += dp [ i - 1 ] [ a ] [ k - c[ j ] ] (当满足 s [ j ] & s [ a ] == 0 时),最后循环所有 way 的 dp [ n ] [ way ] [ k ] 求得总和即为答案。数组要开 long long,得出的结果也要用 long long 保存,因为情况会爆 int。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; int n, m, k, way; int c[600], s[600]; ll dp[100][600][25]; void make_num() { for (int i = 0; i < (1 << m); ++i) { int num = i, one = 0; int temp = 0, last = num % 2; num /= 2; if (last) ++one; while (num) { if (num % 2) ++one; if (last && (num % 2)) { temp = 1; break; } last = num % 2; num /= 2; } if (temp) continue; else { ++way; c[way] = one; s[way] = i; } } } void solve() { memset(dp, 0, sizeof(dp)); dp[0][1][0] = 1; for (int i = 1; i <= n; ++i) { for (int kk = 0; kk <= k; ++kk) { for (int p = 1; p <= way; ++p) { if (c[p] > kk) continue; for (int q = 1; q <= way; ++q) { if (!(s[p] & s[q])) { dp[i][p][kk] += dp[i - 1][q][kk - c[p]]; } } } } } ll res = 0; for (int i = 1; i <= way; ++i) { res += dp[n][i][k]; } printf("%lld\n", res); } int main() { while (~scanf("%d%d%d", &n, &m, &k)) { if (n < m) swap(n, m); way = 0; make_num(); solve(); } return 0; }
相关推荐
ASSIGNMENT的详细要求
useless assignment answer
Aurora中 Lane Assignment分配的小tips,已经验证即使Aurora中分配错误的channal,也能正确传输数据。
CS193P IOS APPLICATION DEVELOPMENT,iphone development Assignment 1, Reproduce the demonstration (building a calculator) given in class.
Assignment Information Theory
东北大学需求分析Assignment 2 solution 东北大学需求分析Assignment 2 solution 东北大学需求分析Assignment 2 solution 东北大学需求分析Assignment 2 solution 东北大学需求分析Assignment 2 solution东北大学...
编译原理 作业 Assignment2
comp2396 assignment1
北航2019年算法课的课后作业。仅供参考。Assignment_1!Assignment_1!Assignment_1!
Assignment4_2.zip
Assignment机器学习的代码
It is not what you think it is
the programs deal with discrete to frequency transformation (DTFT function)
这是我从国外知名大学cs专业留学的同学那里收集来的作业资料(英文原版): 【留学生作业代写资料assignment英文原版】Python作业之CSCI 3151: Assignment 2
A practise assignment
课程作业是让人头疼的事,今天带来Assignment C++课程作业,希望对你有所帮助
Cooperation Aware Task Assignment in Spatial Crowdsourcing.pdf
assignment problems for chemistry students
北航计算机研究生课程 算法设计与分析 Assignment_1
实现图像处理