程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3802 Easy 2048 Again ( 狀態壓縮 )

ZOJ 3802 Easy 2048 Again ( 狀態壓縮 )

編輯：C++入門知識

ZOJ 3802 Easy 2048 Again ( 狀態壓縮 )

題目鏈接~~>

做題感悟：這題很經典，需要模擬一下找規律，還是那句話遇到題自己應該手動推一下。

解題思路：

這題如果手動推幾組數據的話就應該發現，如果放進隊列的元素是遞減的話，這樣才可以連續合並，如果隊列中有 a ,b , a < b 那麼 a 前面的必定不會與 b 經過合並再合並，因為越合並越大，so ~> 隊列中最多才存 12 個數，可以用狀態壓縮壓縮一下。注意要用滾動數組，不用可能超時。

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std  ;
#define INT __int64
#define L(x)  (x * 2)
#define R(x)  (x * 2 + 1)
const int INF = 0x3f3f3f3f ;
const double esp = 0.0000000001 ;
const double PI = acos(-1.0) ;
const int mod = 1000000007 ;
const int MY = (1<<13) + 5 ;
const int MX = 500 + 5 ;
const int MS = 13 ;
int n ;
int g[MX] ,dp[2][MY] ;
int main()
{
    int Tx ;
    scanf("%d" ,&Tx) ;
    while(Tx--)
    {
        scanf("%d" ,&n) ;
        for(int i = 1 ;i <= n ; ++i)
            scanf("%d" ,&g[i]) ;
        memset(dp ,-1 ,sizeof(dp)) ;
        dp[0][0] = 0 ;
        for(int i = 1 ;i <= n ; ++i)
          for(int S = 0 ;S <= MY ; ++S)
            if(dp[(i-1)%2][S] != -1) // 由前一行的合法狀態遞推第 i 行
            {
                dp[i%2][S] = max(dp[i%2][S] ,dp[(i-1)%2][S]) ;   // 不拿
                int k ,key ,sum ,ret ,temp ;
                if(S)
                {
                    for(int k = 0 ;k <= 12 ; ++k)     // 計算隊列中的最小的元素
                      if(S&(1< g[i])  // 放入隊列
                    dp[i%2][g[i] + S] = max(dp[i%2][g[i] + S] ,dp[(i-1)%2][S] + g[i]) ;
            }
        int ans = 0 ;
        for(int S = 0 ;S <= MY ; ++S)
           ans = max(ans ,dp[n%2][S]) ;
        printf("%d\n" ,ans) ;
    }
    return 0 ;
}