作者mantour (朱子)
看板Prob_Solve
標題Re: [問題] 填色問題
時間Mon Sep 21 01:14:39 2009
我的方法應該就是seanwu版友說的dp[6][4][4][4][4]
不過稍微調整了一下(不然要寫很多層迴圈)
我是設int dp[6*4*4*4*4]
dp[a*4*4*4*4+b*4*4*4+c*4*4+d*4*+e] 代表本來的dp[a][b][c][d][e]
然後DP的部份這樣寫
dp[i]=Σ dp[i-4*4*4*4-pow(4,j)-pow(4,k)] , where:
j,k
j=0~3,k=0~3,k>j,
(i%pow(4,j+1))/pow(4,j)>0,
(i%pow(4,k+1))/pow(4,k)>0
完整的code如下：
http://nopaste.info/686bd47e45.html
算出來是1860，不知道這樣有沒有什麼錯誤的地方？
#include<iostream>
using namespace std;
int pow(int i,int n)
{
int p=1;
for(int j=0;j<n;j++)
{
p=p*i;
}
return p;
}
int main()
{
int dp[6*4*4*4*4];
int a[4];
for(int i=0;i<6*4*4*4*4;i++)
{
dp[i]=0;
}
for(int i=0;i<4;i++)
{
for(int j=i+1;j<4;j++)
{
dp[pow(4,i)+pow(4,j)]=1;
}
}
for(int i=4*4*4*4;i<6*4*4*4*4;i++)
{
for(int j=0;j<4;j++)
{
for(int k=j+1;k<4;k++)
{
if((i%pow(4,j+1))/pow(4,j)>0&&(i%pow(4,k+1))/pow(4,k)>0)
{
dp[i]+=dp[i-4*4*4*4-pow(4,j)-pow(4,k)];
}
}
}
}
cout<< dp[5*4*4*4*4+3*4*4*4+3*4*4+3*4+3]<<endl;
return 0;
}
※ 引述《raincole (冷雨)》之銘言：
: ※ [本文轉錄自 puzzle 看板]
: 作者: raincole (冷雨) 看板: puzzle
: 標題: [問題] 填色問題
: 時間: Wed Sep 16 07:36:52 2009
: 有一張6*4的方格紙，將其中12格塗黑，使每列皆有2格、每行皆有3格為黑。
: 問有多少種上色方法？
: 原方格紙：
: □□□□
: □□□□
: □□□□
: □□□□
: □□□□
: □□□□
: 其中一種上色方法：
: ■■□□
: □■■□
: □□■■
: ■■□□
: ■□□■
: □□■■
: 這題有沒有什麼方法可以計算？
: 又，如果每列要求的黑格數是不等的呢？（每行仍然相等）
: 版友rehearttw提出交換法，
: 但假設我一開始的盤面是這樣：
: □■■□
: □■■□
: □■■□
: ■□□■
: ■□□■
: ■□□■
: 交換以後就會產生重複解了...
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.213.158
※ 編輯: mantour 來自: 140.112.213.158 (09/21 01:15)
※ 編輯: mantour 來自: 140.112.213.158 (09/21 01:28)
1F：推 raincole:嗯好方法...如果只開一維陣列在壓縮的話也可以應付黑格數 09/21 01:25
2F：→ raincole:不等的情況而不浪費空間了，這在ACM11600有出現 09/21 01:26
3F：→ raincole:謝謝解答 09/21 01:26
4F：推 ledia:btw, 如果只算 pow of 4, 不如用 shift 09/21 02:14
5F：→ mantour:對耶 謝謝l大的提點 09/21 19:21
6F：推 terrorlone:此題的一個簡單解答貼於 Puzzle 版 12/22 06:09