• <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 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



69久久夜色精品国产69|
久久精品亚洲福利|
97精品伊人久久大香线蕉|
狠狠色丁香婷婷久久综合|
少妇人妻88久久中文字幕|
亚洲国产成人久久综合一
|
久久人妻少妇嫩草AV蜜桃|
三上悠亚久久精品|
久久这里有精品视频|
精品国产乱码久久久久久1区2区|
久久国产精品成人免费|
亚洲欧美精品一区久久中文字幕|
久久久无码精品亚洲日韩蜜臀浪潮
|
亚洲AV无码1区2区久久|
久久久免费观成人影院|
人人狠狠综合久久88成人|
蜜臀久久99精品久久久久久|
久久久噜噜噜www成人网|
久久国内免费视频|
久久国产香蕉一区精品|
国产精品久久国产精品99盘|
久久亚洲中文字幕精品一区|
国产综合精品久久亚洲|
国产精品免费看久久久|
色偷偷88888欧美精品久久久|
久久无码一区二区三区少妇|
国产人久久人人人人爽|
久久无码专区国产精品发布|
久久精品国产色蜜蜜麻豆|
亚洲国产精品久久久久网站
|
国产国产成人久久精品|
国产精品国色综合久久|
久久综合综合久久综合|
中文国产成人精品久久不卡|
久久综合久久综合亚洲|
少妇被又大又粗又爽毛片久久黑人|
国产99久久久国产精品～～牛|
69国产成人综合久久精品|
国产精品毛片久久久久久久|
91视频国产91久久久|
伊人久久大香线蕉影院95|