• <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++博客 ::
首頁 ::
新隨筆 ::
聯(lián)系 ::
聚合
 ::
管理 ::


			
			
				

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

            

			            		
		
            
	
            

            


            


            
	
					

            
	
	
	
            
		
             1//狀態(tài)壓縮
             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//生成每行的所有合法狀態(tài)
            15//參數(shù)：pos 代表行 illegal代表不合法的狀態(tài)(源行為0的狀態(tài))
            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的狀態(tài)
            24            continue;
            25        if ( state & illegal )    //去除原為0的狀態(tài)
            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    //初始化：首行的每個合法狀態(tài)必為1
            39    for ( i = 0; i < item[0].m_size; ++i )
            40        dp[0][i] = 1;
            41
            42    //狀態(tài)方程：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            //取反狀態(tài)
            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 巫 閱讀(347) 評論(0)  編輯 收藏 引用  所屬分類: DP 
	
            

            







            
	    
    




            






            

				

            



    
    







            
	   
	



久久久无码精品午夜|
欧美伊香蕉久久综合类网站|
久久久久一级精品亚洲国产成人综合AV区|
精品久久777|
午夜精品久久久久久影视riav|
伊人久久大香线蕉无码麻豆|
久久精品蜜芽亚洲国产AV|
成人久久精品一区二区三区|
久久亚洲高清综合|
日本人妻丰满熟妇久久久久久|
久久99毛片免费观看不卡|
亚洲婷婷国产精品电影人久久|
久久精品国产亚洲AV电影|
国产精品一区二区久久精品无码|
成人综合久久精品色婷婷
|
久久婷婷色综合一区二区|
精品久久久中文字幕人妻|
人人狠狠综合久久亚洲婷婷|
国产精品99久久久精品无码|
国产91色综合久久免费分享|
欧美精品乱码99久久蜜桃|
97超级碰碰碰碰久久久久|
久久久无码人妻精品无码|
久久精品国产亚洲AV久|
色婷婷狠狠久久综合五月|
国产成人综合久久久久久
|
99久久国产热无码精品免费|
午夜精品久久久久久|
久久99国产精品99久久|
久久香蕉国产线看观看精品yw|
久久综合给合综合久久|
久久99久久成人免费播放|
韩国三级大全久久网站|
国产精品青草久久久久婷婷
|
日本国产精品久久|
99久久无码一区人妻|
国产福利电影一区二区三区久久久久成人精品综合
|
久久国产精品免费一区|
2021国产成人精品久久|
久久狠狠色狠狠色综合|
成人国内精品久久久久影院VR|