首页 > 代码库 > SRM709 div1 Xscoregame（状压dp）

SRM709 div1 Xscoregame（状压dp）

2024-10-09 10:22:02   217人阅读

题目大意：

给定一个序列a，包含n个数（n<=15)，每个数的大小小于等于50

初始时x = 0，让你每次选a中的一个数y，使得x = x + x^y

问如何安排选择的次序，使得最终结果最大。

 

考虑状态压缩，dp[S]表示选了S状态的数的最大结果

我们发现这样做是错误的，因为目前的最大并不意味最后的最大

但是我们会发现，y最大只有50，所以x的大于63的部分不会发生变化，只有小于64的部分会受到y异或的结果

所以我们用dp[S][t]表示：选了S状态的数，小于64部分为t是否可行

然后用dp[S][64]代表大于64部分的大小

选第i个数加入的转移就是，先求出小于64部分与A[i]异或的最大值Max

然后大于64部分的大小就是2*dp[S][64] + (Max>>6)

找到所有小于64部分的异或>>6大于1的值，然后更新那些可行的状态即可

最后输出就是大于64的部分<<6再加上小于64部分最大的可行解

 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <queue>
using namespace std;
void print(int x){
    cout<<"*";
    while(x){
        if(x&1) cout<<1;
        else cout<<0;
        x>>=1;
    }
    cout<<endl;
}
long long dp[(1<<15) + 1][100];
queue<int> Q;
int vis[(1<<15) + 1];

void Find(int S){
    for(int i = 0; i < 64; i++) if(dp[S][i]) cout<<i<<" "; cout<<dp[S][64];
    cout<<endl;
}

class Xscoregame {
    public:
    int getscore(vector<int> A) {
        int n = A.size();
        Q.push(0);
        dp[0][0] = 1;
        while(!Q.empty()){
            int S = Q.front(); Q.pop();
            //print(S);
            //Find(S);
            for(int i = 0; i < n; i++){
                if(S&(1<<i)) continue;
                int Max = 0;
                for(int j = 0; j < 64; j++){
                    if(!dp[S][j]) continue;
                    Max = max(Max, j + (j^A[i]));
                }
                if(Max == 0) continue;
                if(dp[S|(1<<i)][64] > 2*dp[S][64] + (Max>>6)) continue;
                if(dp[S|(1<<i)][64] != 2*dp[S][64] + (Max>>6))
                    for(int j = 0; j < 64; j++) dp[S|(1<<i)][j] = 0;
                if(!vis[S|(1<<i)]) Q.push(S|(1<<i)); vis[S|(1<<i)] = 1;
                dp[S|(1<<i)][64] = 2*dp[S][64] + (Max>>6);
                for(int j = 0; j < 64; j++){
                    if(!dp[S][j]) continue;
                    int temp = j + (j^A[i]);
                    if((temp>>6) == (Max>>6)) dp[S|(1<<i)][temp&63] = 1;
                }
            }
        }
        long long ans = 0, temp = 0;
        for(int i = 63; i >= 0; i--) if(dp[(1<<n)-1][i]) { temp = i; break; }
        ans += (dp[(1<<n)-1][64]<<6) + temp;
        return ans;
    }
};

 

SRM709 div1 Xscoregame（状压dp）


联系
我们