作者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