题解：P7093 [CERC2014] Can't stop playing

· · 题解

建议标签：状压 DP、记忆化搜索。\ 通过机房某几位大佬了解了这题，在一节英语课内想到正解但是不影响我被卡一个晚上（虚\ 所以应该算是水紫吧？应该算吧？

分析：

我们尝试从无解条件入手。\ 显然地，当这些数和不为 2 的整数次幂时肯定无解。\ 同时，我们容易注意到一件事情：一个数经历合并后只会越来越大。\ 这条显然的性质有什么用呢？\ 放到具体情境中，如果一个数两边的数都比他大，那么再怎么消，两边的数都只可能更大，又不会消失，导致中间的数永远无法合并，即该情况无解。\ 又考虑到相同的数相邻会合并，这意味着，序列的实时状态是单峰的，前半严格递增，后半严格递减。\ 因为题目保证总和不超过 2^{13}，我们很容易联想到将序列的状态拆成左右两半，状态压缩为二进制数。\ 那么，如果我们要从一端插入一个数 a_i，为避免状态无解，设这一半状态压缩为 x，则需要满足 a_i\le lowbit(x)。\ 手玩一下发现，不考虑两半的最大数合并，我们从一端插入一个数对状态的影响正好满足二进制加法！\ 那么，如果考虑两半最大数的合并呢？\ 我们牺牲空间，钦定左半边状态最高位保持更大（右半边也行，事实上由于总能找到左右相反的方案，左与右没有影响），对值域内的所有数预处理下二进制最高位。每次转移状态后，比较两边最高位，如果右边最高位大于等于左边最高位，就把右边的最高位挪到左边去。\ 因此，我们考虑记忆化搜索实现状压 DP，搜索当前编号 i 和左状态 lft，因为到第 i 位两半状态总和总是等于第 i 位的前缀和，我们利用前缀和求出右状态 rit，按照合并规则进行状态转移即可。

实现细节：

  3. 如果同时枚举左右状态，O(2^{26}) 容易引起常数爆炸。考虑储存前缀和，枚举左状态，前缀和减去左状态得到右状态。两半最高位合并后显然需要更新右状态的值。这样的作法大概 O(2^{13}n)。

代码：

#include <bits/stdc++.h>
using namespace std;
int t,n,a[1145],sum[1145],high[(1<<13)+10],dp[1145][(1<<13)+10],nxt[1145][(1<<13)+10];
inline int lowbit(int x){
    return x&(-x);
}
inline bool dfs(int now,int lft){
    int rit=sum[now-1]-lft,h1=-1,h2=-1;
    h1=high[lft];
    h2=high[rit];
    if(h1==h2&&h1>=0) lft+=(1<<h1);
    if(h1<h2) lft+=(1<<h2);
    rit=sum[now-1]-lft;//最高位合并，更新rit 
    if(now==n+1){
        if(!lft||lft==sum[n]||lft==sum[n]>>1) return 1;//3种成功情况
        else return 0;
    }
    if(dp[now][lft]!=-1) return dp[now][lft];//返回已记忆结果 
    int res=0;
    dp[now][lft]=0;
    if(!lft||a[now]<=lowbit(lft)){
        res=dfs(now+1,lft+a[now]);
        if(res){
            dp[now][lft]=1;
            nxt[now][lft]=0;
        }//记录方向 
    }//左侧可插入 
    if(!rit||a[now]<=lowbit(rit)){
        res=dfs(now+1,lft);
        if(res&&!dp[now][lft]){
            dp[now][lft]=1;
            nxt[now][lft]=1;
        }//记录方向，向左能成功就可以不动 
    }//右侧可插入 
    return dp[now][lft];
}
inline void print(int now,int lft){
    int rit=sum[now-1]-lft,h1=-1,h2=-1;
    h1=high[lft];
    h2=high[rit];
    if(h1==h2&&h1>=0) lft+=(1<<h1);
    if(h1<h2) lft+=(1<<h2);//最高位合并，但这里不需要更新rit 
    if(now==n+1) return;
    if(nxt[now][lft]) cout<<'r';
    else cout<<'l';//根据方向打印 
    print(now+1,nxt[now][lft]?lft:lft+a[now]);//沿着记录方向搜索打印 
}
inline void solve(){
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];//前缀和 
    }
    if(sum[n]!=lowbit(sum[n])){
        puts("no");
        return;
    }//无解情况：和不为2的整数幂 
    for(int i=0;i<=n;++i){
        for(int j=0;j<=sum[n];++j) dp[i][j]=-1;
    }//dp置初值 
    if(dfs(1,0)){
        print(1,0);
        puts("");
    } 
    else puts("no");
}
int main(){
    high[0]=-1;//不要漏！！！ 
    for(int i=1;i<=(1<<13);++i){
        for(int j=0;j<=13;++j) high[i]=max(high[i],((i>>j)&1)*j);
    }//预处理最高位 
    cin>>t;
    while(t--) solve();
    return 0;
}