gzwzm06
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks
POJ 3254 Corn Fields
 1//状态压缩
 2#include <cstdio>
 3
 4int N, M;
 5
 6struct ITEM
 7{
 8    int m_arr[1024];
 9    int m_size;
10}item[13];
11
12int dp[13][1024];
13
14//生成每行的所有合法状态
15//参数：pos 代表行 illegal代表不合法的状态(源行为0的状态)
16void 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
34void 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
68int 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 巫 阅读(341) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理