2019牛客暑期多校训练营（第三场）I Median

题意：给出n-2的中位数序列b，b[i]代表原序列中(a[i],a[i+1],a[i+2])的中位数，求a。

解法：比赛的时候没做出来，赛后看题解的。解法跟网上各位大佬一样：首先要证明其实原序列a中的每一个元素都是来自于b中与其相关的3个数（a[i] from b[i-2],b[i-1],b[i]），那么根据这个我们就可以考虑用dp来构造方案了。

dp的实现网上更多是dp[i][j][k]代表前i-2序列已经合法且第位置i填相关数中的第j小，位置i-1填相关数中的第k小使得前i序列都是合法的。但是我感觉这样设计处理起来有点不方便。

我的dp是，dp[i][j][k]代表前i-2合法，位置i填 b(i-j) 位置i-1填 b(i-1-k) 使得前i序列合法。当然要输出方案的话还需要一个g[i][j][k]代表当前状态从那个状态转移而来，因为当前的k已经记录了i-1的j，所以只有再记录一个l作为i-1的k就能得到上一个状态。

那么状态转移方程就是：f[i][j][k]=1;且g[i][j][k]=l; (f[i-1][k][l] && calc(b[i-j],b[i-1-k],b[i-2-l])==b[i-2]) ；

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],f[N][3][3],g[N][3][3];

int calc(int x,int y,int z) {
    int t[3]; t[0]=x; t[1]=y; t[2]=z;
    sort(t,t+3);
    return t[1]; 
}

void print(int i,int j,int k) {
    if (i==2) {
        printf("%d %d ",b[i-1-k],b[i-j]);
        return;
    }
    print(i-1,k,g[i][j][k]);
    printf("%d ",b[i-j]);
}

int main()
{
    int T; cin>>T;
    while (T--) {
        scanf("%d",&n);
        for (int i=1;i<=n-2;i++) scanf("%d",&b[i]);
        for (int i=0;i<=n;i++) for (int j=0;j<=2;j++) for (int k=0;k<=2;k++) f[i][j][k]=0;
        for (int i=1;i<=2;i++) for (int j=0;j<=2;j++) for (int k=0;k<=2;k++) 
            if (i-j>=1 && i-1-k>=1) f[i][j][k]=1;
        
        bool ok=0; int rj,rk;
        for (int i=3;i<=n;i++) 
            for (int j=0;j<=2;j++)
                for (int k=0;k<=2;k++)
                    for (int l=0;l<=2;l++)
                    if (f[i-1][k][l] && calc(b[i-j],b[i-1-k],b[i-2-l])==b[i-2]) {
                        f[i][j][k]=1;
                        g[i][j][k]=l;
                        if (i==n) {
                            ok=1; rj=j; rk=k;
                        }
                    }
        
        if (!ok) { puts("-1"); continue; }
        print(n,rj,rk); puts(""); 
    }
    return 0;
}