2010年1月18日星期一.sgu220 sgu221
sgu220:n*n的棋盤上放k個象 (n <= 10)
終究還不全是自己想出來的，看到一個提示，放在黑格和白格上的象互不相關。
然后我就開始想狀態壓縮dp。。。
注意到
+ + + + + + ++ + + + + + ++ + + + + + ++ + + +如果想對+上邊放車的情況進行dp，可以把黑格變成這樣：
+++++++++++++++++++++++++然后就可以使用放車的方法進行二維dp了。
可惜老夫想歪了，雖然也過了，但是是狀態壓縮的，只能對于這題有用，對sgu221就不行了.
狀態壓縮見代碼:
int c[bin(N)],bsp,wsp;
LL black[N],white[N];
LL dpblack[N][N][bin(N)], cb[N];
LL dpwhite[N][N][bin(N)], cw[N];
//http://m.shnenglu.com/schindlerlee
void preproc()
{
int i;
full = bin(n) - 1;
bsp = wsp = 1;
for (i = 1; i < n; i += 2) {
black[bsp++] = rev(bin(i) - 1) & full;
black[bsp++] = rev(bin(i) - 1) & full;
}
if (i == n) { black[bsp++] = rev(bin(i) - 1) & full; }
for (i = 2; i < n; i += 2) {
white[wsp++] = rev(bin(i) - 1) & full;
white[wsp++] = rev(bin(i) - 1) & full;
}
if (i == n) { white[wsp++] = rev(bin(i) - 1) & full; }
for (i = 1;i <= full;i++) {
int t = i;
while (t > 0) {
c[i] += t & 1;
t >>= 1;
}
}
}
void proc(LL dp[N][N][bin(N)], int terrain[N], int sp,LL res[N])
{
int i, line, s;
dp[0][0][0] = 1;
for (line = 1; line <= sp; line++) {
for (s = 0; s <= full; s++) { dp[line][c[s]][s] += dp[line-1][c[s]][s]; }
for (i = 1; i <= full; i <<= 1) {
if (i & terrain[line]) continue;
for (s = 0; s <= full; s++) {
if(i & s) continue;
dp[line][c[i|s]][i|s] += dp[line-1][c[s]][s];
}
}
}
for (i = 0;i <= k && i <= sp;i++) {
for (s = 0;s <= full;s++) {
res[i] += dp[sp][i][s];
}
}
}
int main()
{
int i;
scanf("%d%d", &n, &k);
preproc();
proc(dpblack, black, bsp-1, cb);
proc(dpwhite, white, wsp-1, cw);
LL res = 0;
for (i = 0;i <= k;i++) {
if(i < bsp && k-i < wsp) // really important
res += cb[i] * cw[k-i];
}
cout << res << endl;
return 0;
}
其實可以發現
如果f(i,j)表示前i行放j個
那么f[i][j] = f[i-1][j] + f[i-1][j-1] * (n(i) - (j-1))
然后程序就變成了這個樣子。。
const int N = 101;
LL fb[N][N],fw[N][N];
LL black[N],white[N];
int wsp,bsp,n,k;
void preproc()
{
int i;
bsp = wsp = 1;
for (i = 1; i < n; i += 2) {
black[bsp++] = i;
black[bsp++] = i;
}
if (i == n) { black[bsp++] = i; }
for (i = 2; i < n; i += 2) {
white[wsp++] = i;
white[wsp++] = i;
}
if (i == n) { white[wsp++] = i; }
bsp--,wsp--;
}
void proc(LL dp[N][N],LL terrain[N],int sp)
{
int i,j;
dp[0][0] = 1;
for (i = 1;i <= sp;i++) {
for (j = 0;j <= terrain[i];j++) {
dp[i][j] = dp[i-1][j] + dp[i-1][j-1] * (terrain[i] - j + 1);
}
}
}
int main()
{
int i;
scanf("%d%d",&n,&k);
preproc();
proc(fb,black,bsp);
proc(fw,white,wsp);
LL res = 0;
for (i = 0;i <= k;i++) {
res += fb[bsp][i] * fw[wsp][k-i];
}
cout << res << endl;
return 0;
}
sgu221:n*n的棋盤上放k個象 (n <= 50)
這題由于數據量變大了，所以需要高精度的模板，本人是上的java
//http://m.shnenglu.com/schindlerlee/
public class Solution {
static int black[], white[];
static int wsp, bsp, n, k;
static void preproc() {
int i;
bsp = wsp = 1;
for (i = 1; i < n; i += 2) {
black[bsp++] = i;
black[bsp++] = i;
}
if (i == n) {
black[bsp++] = i;
}
for (i = 2; i < n; i += 2) {
white[wsp++] = i;
white[wsp++] = i;
}
if (i == n) {
white[wsp++] = i;
}
bsp--;
wsp--;
}
public static void main(String[] args) {
Scanner cin = new Scanner(
new BufferedReader(
new InputStreamReader(System.in)));
int i, j;
n = cin.nextInt();
k = cin.nextInt();
if(k >= n * 2) {
System.out.println("0");
return;
}
black = new int[456];
white = new int[456];
BigInteger[][] fb = new BigInteger[456][456];
BigInteger[][] fw = new BigInteger[456][456];
preproc();
for (i = 0; i < 456; i++) {
for (j = 0; j < 456; j++) {
fb[i][j] = BigInteger.ZERO;
fw[i][j] = BigInteger.ZERO;
}
}
fb[0][0] = BigInteger.ONE;
for (i = 1; i <= bsp; i++) {
fb[i][0] = BigInteger.ONE;
for (j = 1; j <= black[i]; j++) {
BigInteger tmp = BigInteger.valueOf(black[i] - j + 1);
fb[i][j] = fb[i - 1][j].add(fb[i - 1][j - 1].multiply(tmp));
}
}
fw[0][0] = BigInteger.ONE;
for (i = 1; i <= wsp; i++) {
fw[i][0] = BigInteger.ONE;
for (j = 1; j <= white[i]; j++) {
BigInteger tmp = BigInteger.valueOf(white[i] - j + 1);
fw[i][j] = fw[i - 1][j].add(fw[i - 1][j - 1].multiply(tmp));
}
}
BigInteger res = BigInteger.ZERO;
for (i = 0; i <= k; i++) {
res = res.add(fb[bsp][i].multiply(fw[wsp][k - i]));
}
System.out.println(res);
}
}