PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 填色問題

看板Prob_Solve (計算數學 Problem Solving)作者mantour (朱子)時間15年前 (2009/09/21 01:14)推噓3(3推 0噓 3→)

留言6則, 4人參與討論串2/2 (看更多)

我的方法應該就是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)