[状压dp] CF1342F

· · 个人记录

思路

此类状压题的状态设计比较巧妙，想到就做完了。不过还是有套路的。

很容易想到让 f 的值为最小操作次数，但这样状态必须有一维用于表示上升序列的最后一位，直接数值表示肯定不行，用二进制表示的话会超时。因此这种思路是不行的。

套路：那么让最小操作次数变成 f 中的一维，这样就变成维护可行性了，然后 f 的值就可以是上升序列的最后一位的数值了，这样复杂度就与 a 大小无关了。

尝试考虑元素 i 对 f 的影响，我们可以将它向某个元素合并，也可以让若干元素向它合并。注意此时就不能一元素一个元素的考虑了，否则我们还需要记录此前元素合并起来的值，那就违背我们本意了。

套路：所以换种想法，我们一位一位考虑最终上升序列的值，这样就避免了上述问题，也就是说一次性抽出 a 中元素合并，并加入上升序列中，一个元素能被抽出来，需要它此前未被操作过，因此可以开一维状压 a 中元素是否被操作。

还有一点需要注意：即所有元素之间的相对关系。我们将若干元素合并，一定是把它们归于其中一个元素上的，就叫它“集中点”。由于所有的集中点都不移动，所以“集中点”的相对关系是不变的！那么还需开一维记录最后一个“集中点”在原序列的下标，新的“集中点”的下标肯定不能在它的前面。

所以定义：f_{S,i,j} 表示操作了的集合为 S，最后一个集中点的原下标为 i，最少操作次数为 j 时，最终上升序列的最后一位的最小值。

转移不说了，按照上面的定义严格来做就好啦。

复杂度看似是 O(3^n{n^3})，即枚举当前状态、枚新加的子集、枚举这个子集的集中点。但是我们发现，每次新加上的子集的集合点不需枚举，可以贪心的取最靠左的，这样一定不劣。

于是复杂度为 O(3^nn^2)，不难发现跑不满，有很多无效状态会被剪掉，再加上本题时限较大，可过。

CODE

码了好久啊。。。感觉敲完后码力会得到提升？

#include<bits/stdc++.h> 
using namespace std; 

#define lowbit(a) ((a) & -(a)) 
const int N = 16, inf = 2e9; 
int t, A, n, a[N], f[1 << N][N + 5][N + 5], sm[1 << N], id[1 << N], mx[N]; 
int ans, dc, pc, B; 
int num[N + 5];
pair<int, int> p[1 << N];
struct edge{int x, y, z;}lst[1 << N][N + 5][N + 5];

//集合、总共几个、集中点，为了方便转移将第三维+1 
//代码极其丑陋，建议自己打或者看题解的（ 

inline int get(string s){
    int res = 0;
    for(int i = 0; i < n; ++i)
        if(s[i] == '1') res += (1 << i);
    return res;
}
inline void print(int S, int S2, int p){ 
    if(!S2) return ;
    int cnt = 0, cnt2 = 0;
    for(int i = 0; i < n; ++i)
        if(!((B >> i) & 1)) num[i] = ++cnt;

    S2 = S2 ^ S, cnt = 0;
    for(int i = 0; i < n; ++i)
        if((S2 >> i) & 1){
            if(i == p) continue;
            printf("%d %d\n", num[i] - cnt, num[p] - cnt2);
            ++cnt, cnt2 += (i < p);
        }
    B ^= (S2 ^ (1 << p));
}
signed main(){ 
    for(int i = 0; i < N; ++i) id[1 << i] = i; 

    cin >> t;
    while(t--){
        scanf("%d", &n);  
        A = (1 << n) - 1;  

        for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
        for(int i = 0; i < 1 << n; ++i){  
            sm[i] = 0;  
            for(int j = 0; j < n; ++j)  
                if((i >> j) & 1) sm[i] = sm[i] + a[j];
            for(int j = 0; j <= n; ++j)
                for(int k = 0; k <= n; ++k)
                    f[i][j][k] = inf;
        }
        f[0][0][0] = 0;

        for(int S = 0, SS, p; S < 1 << n; ++S){
            SS = A ^ S;
            for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j){
                    if(f[S][i][j] == inf) continue;
                    for(int S2 = SS; S2; S2 = (S2 - 1) & SS){
                        if(((j > 0) && (!((S2 >> j) << j))) || (f[S][i][j] >= sm[S2])) continue;
                        p = id[lowbit((S2 >> j) << j)];
                        if(f[S ^ S2][i + 1][p + 1] > sm[S2]){
                            f[S ^ S2][i + 1][p + 1] = sm[S2];
                            lst[S ^ S2][i + 1][p + 1] = {S, i, j};
                        }
                    }
                }
        }

        bool flag = false;
        for(int i = n; i >= 0 && !flag; --i)
            for(int j = 1; j <= n && !flag; ++j) 
                if(f[A][i][j] ^ inf){
                    flag = true; pc = 0;
                    printf("%d\n", n - i);
                    int x = A, y = i, z = j;
                    do{
                        edge P = lst[x][y][z];
                        p[++pc] = {x, z - 1};
                        x = P.x, y = P.y, z = P.z;
                    }while(x);
                    p[++pc] = {0, 0}, B = 0;
                    while(pc) 
                        print(p[pc].first, p[pc - 1].first, p[pc - 1].second), --pc;
                    break; 
                }
    }
    return 0; 
}