• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	

            
	
            
		
            
			
				
            gzwzm06
            
				
            
			            		
		
            
	
            

            

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


			
			
				

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

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
             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 巫 閱讀(351) 評論(0)  編輯 收藏 引用  所屬分類: DP 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



97精品国产97久久久久久免费|
热99RE久久精品这里都是精品免费
|
91久久九九无码成人网站|
国产欧美久久一区二区|
狠狠色综合网站久久久久久久|
91久久精品国产成人久久|
成人综合久久精品色婷婷|
精品久久久久久国产潘金莲|
91精品国产高清久久久久久91|
久久亚洲中文字幕精品一区|
国产精品欧美久久久天天影视|
久久久久久极精品久久久|
99久久精品国产高清一区二区|
久久综合成人网|
久久九九全国免费|
国内精品伊人久久久久777|
97久久精品人人做人人爽|
久久婷婷五月综合97色直播|
亚洲一本综合久久|
国产精品美女久久久久久2018|
久久婷婷五月综合国产尤物app
|
日日狠狠久久偷偷色综合免费|
欧美喷潮久久久XXXXx|
久久亚洲av无码精品浪潮|
色成年激情久久综合|
久久久久久国产精品免费无码|
亚洲精品乱码久久久久久蜜桃|
精品多毛少妇人妻AV免费久久|
久久99国产综合精品女同|
久久香综合精品久久伊人|
久久亚洲精品无码观看不卡|
狠狠久久综合|
久久精品国产只有精品66|
国产亚洲精午夜久久久久久|
久久亚洲国产精品一区二区|
99久久精品国产麻豆|
久久免费美女视频|
国产高潮国产高潮久久久91|
大香网伊人久久综合网2020|
超级碰久久免费公开视频|
久久香蕉综合色一综合色88|