欧美中文字幕在线播放,国产午夜精品一区理论片飘花,欧美国产三区

POJ 3254 Corn Fields

//狀態壓縮
2

#include <cstdio>
3

int N, M;
5

struct ITEM
7

{
8

int m_arr[1024];
9

int m_size;
10

}item[13];
11

int dp[13][1024];
13

//生成每行的所有合法狀態
15

//參數：pos 代表行 illegal代表不合法的狀態(源行為0的狀態)
16

void GetState(const int& pos, const int& illegal)
17

{
18

int state, n;
19

n = 0;
21

for ( state = 0; state < (1 << N); ++state ) //從0開始枚舉到(1 << N): N = 3時, 000-->111 ((1 << N)8 - 1)
22

{
23

if ( (state << 1) & state || (state >> 1) & state ) //去除相鄰都為1的狀態
24

continue;
25

if ( state & illegal ) //去除原為0的狀態
26

continue;
27

item[pos].m_arr[n++] = state;
29

}
30

item[pos].m_size = n;
32

}
33

void Solve()
35

{
36

int i, j, k;
37

//初始化：首行的每個合法狀態必為1
39

for ( i = 0; i < item[0].m_size; ++i )
40

dp[0][i] = 1;
41

//狀態方程：dp[i][j] = SUM{dp[i - 1][k]}
43

for ( i = 1; i < M; ++i )
44

{
45

for ( j = 0; j < item[i].m_size; ++j )
46

{
47

dp[i][j] = 0;
48

for ( k = 0; k < item[i - 1].m_size; ++k )
49

{
50

//與上一行沖突
51

if ( item[i].m_arr[j] & item[i - 1].m_arr[k] )
52

continue;
53

dp[i][j] += dp[i - 1][k];
54

}
55

}
56

}
57

int result = 0;
59

for ( i = 0; i < item[M - 1].m_size; ++i )
60

{
61

result += dp[M - 1][i];
62

result %= 100000000;
63

}
64

printf("%d\n", result);
66

}
67

int main()
69

{
70

// freopen("1.txt", "r", stdin);
71

int i, j, state, illegal;
72

scanf("%d %d", &M, &N);
74

for ( i = 0; i < M; ++i )
76

{
77

illegal = 0;
78

for ( j = 0; j < N; ++j )
79

{
80

scanf("%d", &state);
81

//取反狀態
82

illegal = (illegal << 1) + 1 - state;
83

}
84

GetState( i, illegal );
86

}
87

Solve();
89

return 0;
91

}

posted on 2009-05-02 10:51 巫閱讀(355) 評論(0) 編輯收藏引用所屬分類: DP

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 7th GDCPC Problem G: Black Jack ZOJ 3187--Inviting Friends zoj 3201 Tree of tree POJ 3211 Washing Clothes POJ 3254 Corn Fields POJ 3670 Eating Together(最長非遞增（非遞減）子序列) POJ 3661-Running Pku 3494--Largest Submatrix of All 1’s(路徑壓縮) PKU 1964--City Game(棧模擬) POJ 2559--Largest Rectangle in a Histogram(棧模擬)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

gzwzm06

常用鏈接

留言簿(3)

隨筆檔案

文章分類

文章檔案

搜索

最新評論