Re: [問題] 填色問題

[mantour (朱子)]

我的方法應該就是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)
推 raincole:嗯好方法...如果只開一維陣列在壓縮的話也可以應付黑格數
→ raincole:不等的情況而不浪費空間了，這在ACM11600有出現
→ raincole:謝謝解答
推 ledia:btw, 如果只算 pow of 4, 不如用 shift
→ mantour:對耶 謝謝l大的提點
推 terrorlone:此題的一個簡單解答貼於 Puzzle 版