gzwzm06

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理 ::

1 隨筆 :: 52 文章 :: 17 評論 :: 0 Trackbacks

<

2025年11月

>

日

一

二

三

四

五

六

26

27

28

29

30

31

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

1

2

3

4

5

6

常用鏈接

留言簿(3)

隨筆檔案

2009年5月 (1)

文章分類

文章檔案

搜索

最新評論

1.?re: Pku 2774--Long Long Message（后綴樹）
求教大牛，那個Lt屬性是記錄什么的
--dereky
2.?re: POJ 2481(樹狀數組)
@gzwzm06
哦，實在是不好意思，確實是那個地方，現在過了，謝謝了啊。
--Klion
3.?re: POJ 2481(樹狀數組)
你再檢查下，cc[j].m_e == cc[j].m_e這個條件肯定是真的，沒有意義吧
--gzwzm06
4.?re: POJ 2481(樹狀數組)
@gzwzm06
兩個相同一起比較也就是兩個區間是一樣的，起點和終點是相同的，和您的第80行比較的應該是一樣的吧？
--Klion
5.?re: POJ 2481(樹狀數組)
評論內容較長,點擊標題查看
--gzwzm06

POJ 3254 Corn Fields

1

//狀態壓縮
2

#include <cstdio>
3

4

int N, M;
5

6

struct ITEM
7

{
8

int m_arr[1024];
9

int m_size;
10

}item[13];
11

12

int dp[13][1024];
13

14

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

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

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

{
18

int state, n;
19

20

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

28

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

}
30

31

item[pos].m_size = n;
32

}
33

34

void Solve()
35

{
36

int i, j, k;
37

38

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

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

dp[0][i] = 1;
41

42

//狀態方程：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

58

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

65

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

}
67

68

int main()
69

{
70

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

int i, j, state, illegal;
72

73

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

75

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

85

GetState( i, illegal );
86

}
87

88

Solve();
89

90

return 0;
91

}

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

只有注冊用戶登錄后才能發表評論。


相關文章: 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 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品