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

            







            
	    
    




            






            

				

            



    
    







            
	   
	



亚洲国产精品久久久久网站|
91精品国产91久久久久久|
亚洲人成无码久久电影网站|
久久久久久久久波多野高潮|
人妻精品久久久久中文字幕一冢本|
久久夜色精品国产欧美乱|
国产精品99久久久久久猫咪|
少妇人妻综合久久中文字幕|
久久精品中文无码资源站|
久久久久国产|
国内精品伊人久久久久|
久久精品国产亚洲av麻豆蜜芽
|
国产精品久久久久9999高清|
天天综合久久久网|
亚洲女久久久噜噜噜熟女|
久久se精品一区精品二区国产|
久久综合给合久久狠狠狠97色
|
欧美激情精品久久久久|
国产精品久久久久久久app
|
久久久青草青青国产亚洲免观|
久久综合给久久狠狠97色|
午夜肉伦伦影院久久精品免费看国产一区二区三区
|
久久亚洲国产最新网站|
99久久精品免费看国产|
麻豆成人久久精品二区三区免费
|
国内精品久久久久久久97牛牛
|
国产精品99久久精品|
色偷偷88888欧美精品久久久|
久久久久无码中|
精品久久综合1区2区3区激情|
久久成人国产精品二三区|
日本人妻丰满熟妇久久久久久|
久久亚洲高清综合|
国产69精品久久久久99尤物|
精品精品国产自在久久高清|
国产欧美久久一区二区|
久久91精品久久91综合|
久久99国产精品久久久|
亚洲精品国产成人99久久|
亚洲成人精品久久|
国内精品久久久久久久久|