Make It Ascending

_ANIG_ · 2023-10-17 19:57:45 · 个人记录

定义状态 f_{i,S,T} 表示最后一个数以 i 为底，已经用过的集合为 S，最后一个数对应的集合为 S 的方案数。

但是状态数太多。注意到答案很小，所以可以交换答案和状态。

用 f_{i,j,S} 表示最后一个数以 i 为底，当前凑成的序列长度为 j，已经用过的集合为 S，最后一个数最小是多少。

转移直接枚举子集，看是否合法。

复杂度 O(3^nn^3)，可以用前缀和优化到 O(3^nn^2)，求方案就对每个状态记录这个状态是从哪转移过来的。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=17,M=(1<<15)+5;
int n,p[N],f[N][N][M],sm[M],t,lg2[M],g[N][N][M],mk[N],zj[N][N][M];
void pt(int a,int b){
    if(a==b)return;
    int r1=0,r2=0;
    for(int i=1;i<=a;i++)if(!mk[i])r1++;
    for(int i=1;i<=b;i++)if(!mk[i])r2++;
    mk[a]=1;
    cout<<r1<<" "<<r2<<endl;
}
void solve(int floor,int nw,int wz){
    if(floor==0)return;
    int k=g[wz][floor][nw];
    for(int i=1;i<wz;i++){
        if(zj[i][floor-1][nw^k]<sm[k]){
            solve(floor-1,nw^k,i);
            break;
        }
    }
    for(int i=1;i<=n;i++){
        if(k>>i-1&1){
            pt(i,wz);
        }
    }
}
signed main(){
    for(int i=0;i<=15;i++)lg2[1<<i]=i;
    cin>>t;
    for(int ii=1;ii<=t;ii++){
        cin>>n;
        for(int i=0;i<(1<<n);i++)sm[i]=0;
        for(int i=1;i<=n;i++)scanf("%lld",&p[i]);
        for(int i=1;i<(1<<n);i++)sm[i]=sm[(i&-i)^i]+p[lg2[i&-i]+1];
        for(int i=0;i<=n;i++)for(int l=0;l<=n;l++)for(int j=0;j<(1<<n);j++)f[i][l][j]=1e18,zj[i][l][j]=1e18;
        for(int i=0;i<=n;i++)mk[i]=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<(1<<n);j++){
                if(j>>i-1&1)f[i][1][j]=zj[i][1][j]=sm[j],g[i][1][j]=j;
                f[i][1][j]=min(f[i][1][j],f[i-1][1][j]);
            }
        }
        for(int i=2;i<=n;i++){
            for(int l=1;l<=n;l++){
                for(int j=1;j<(1<<n);j++){
                    f[l][i][j]=f[l-1][i][j];
                    if(!(j>>l-1&1))continue;
                    for(int k=j;k;k=(k-1)&j){
                        if(!(k>>l-1&1))continue;
                        if(sm[k]>f[l-1][i-1][j^k]){
                            if(sm[k]<=f[l][i][j])zj[l][i][j]=sm[k],g[l][i][j]=k;
                            f[l][i][j]=min(f[l][i][j],sm[k]);
                        }
                    }
                }
            }
        }
        int ok=0;
        for(int i=n;i>=1;i--){
            for(int j=1;j<=n;j++){
                if(f[j][i][(1<<n)-1]<1e9){
                    cout<<n-i<<endl;
                    solve(i,(1<<n)-1,j);
                    ok=1;
                    break;
                }
            }
            if(ok)break;
        }
    }
}