题意:给出一个n行的棋盘,每行的长度任意,问在该棋盘中放k个车(不能同行或者同列)有多少种放法(n <= 250, 每行的长度 <= 250)。
题目链接:http://acm.sgu.ru/problem.php?contest=0&problem=269
——>>开始的时候冒险用dfs去做,结果TLE了。。。改dp,大数长度开小点WA,开大点MLE……最后改用滚动数组开1000位的大数长度才A掉……
设d[i][j]表示前i行放j个车的方法数,
则状态转移方程为:d[i][j] = d[i-1][j] + d[i-1][j-1] * (b[i] - j + 1);
改滚动数组:d[j] = d[j] + d[j-1] * (b[i] - j + 1);
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>using namespace std;const int maxn = 250 + 2;
const int maxl = 1000;
int b[maxn];struct bign{int len, s[maxl];bign(){memset(s, 0, sizeof(s));len = 1;}bign operator = (int num){len = 0;while(num > 0){s[len++] = num % 10;num /= 10;}if(!len){s[0] = 0;len = 1;}return *this;}bign(int num){*this = num;}bign operator + (const bign& b) const{bign c;c.len = 0;for(int i = 0, g = 0; g || i < max(len, b.len); i++){int x = g;if(i < len) x += s[i];if(i < b.len) x += b.s[i];c.s[c.len++] = x % 10;g = x / 10;}return c;}bign operator * (const bign& b) const{bign c;c.len = len + b.len;for(int i = 0; i < len; i++)for(int j = 0; j < b.len; j++)c.s[i+j] = c.s[i+j] + s[i] * b.s[j];for(int i = 0; i < c.len-1; i++){c.s[i+1] = c.s[i+1] + c.s[i] / 10;c.s[i] = c.s[i] % 10;}while(c.len > 1 && !c.s[c.len-1]) c.len--;return c;}void print(){for(int i = len - 1; i >= 0; i--) printf("%d", s[i]);printf("\n");}
}d[maxn];int main()
{int n, k, i, j;while(scanf("%d%d", &n, &k) == 2){for(i = 1; i <= n; i++) scanf("%d", &b[i]);sort(b+1, b+1+n);memset(d, 0, sizeof(d));d[0] = 1;for(i = 1; i <= n; i++){for(j = k; j >= 1; j--){d[j] = d[j] + d[j-1] * (b[i] - j + 1);}}d[k].print();}return 0;
}