ABC176F Brave CHAIN题解

· · 题解

ABC176F Brave CHAIN题解

Link

很好的一道题。

首先考虑扔三张留两张相当于有一个大小为 2 的包，每次只能装两张牌。

考虑dp。设 f_{i,x,y} 表示前 i+2 张牌（因为三张三张分组所以相当于枚举是哪一组），保留了 x 和 y 的最大收益。

首先有 \mathrm{O(n)} 大常数转移做法，总复杂度 \mathrm{O(n^3)} ，过不去。

首先发现若当前三张 a=A_i,b=A_{i+1},c=A_{i+2} 相同则可以直接删去，容易发现是对的。

然后发现除了上一种情况，与 a,b,c 无关的状态在一次转移中是不会被改变的。那么被改变的状态数就是 \mathrm{O(n)} 的。

这启发我们找只与 a,b,c 相关状态的转移方程。转移中重要的是 a,b,c 而非 x,y 。

对于 a,b,c 相同的情况上面已经去掉了，不考虑。

若有两个数字 a=a,b=a 相同，则若想要增加贡献则必须要找到某一个状态 f_{i-1,x=a,c} 的最大值，然后再加一。

然后是一般的没有贡献的状态更新，容易发现只会跟 a,b,c 相关的状态会被更新。

这两个都是 \mathrm{O(n)} 级别的。

细节的，第一种是查询列最大值，第二种是查询全局最大值以及列最大值。

像背包一样压掉一维，这样才能保证不会被转移的状态不会占用复杂度。

由于两种转移可能同时发生，所以用 vector 来转移。

code

const int N=2e3+5;

int f[N][N];
int mx[N];//行/列最大值，这里这个矩阵是沿对角线对称的

int t[N*3];

struct hhh{
    int u,v,w;
};
vector<hhh>_new;

void clr(vector<hhh>&vec){
    vector<hhh>c;
    swap(c,vec);
}

signed main(){
    int n=read();
    for(int i=1;i<=3*n;i++)
        t[i]=read();
    memset(f,-0x3f,sizeof(f));
    memset(mx,-0x3f,sizeof(mx));
    mx[t[1]]=mx[t[2]]=0;
    f[t[1]][t[2]]=f[t[2]][t[1]]=0;
    int d=0;
    for(int i=3;i<3*n;i+=3){
        int a=t[i],b=t[i+1],c=t[i+2];
        if(a==b&&b==c)
            d++;//全局加
        else{
            int mxx=-inf;
            for(int j=1;j<=n;j++){
                _new.pb({j,a,mx[j]});
                _new.pb({j,b,mx[j]});
                _new.pb({j,c,mx[j]});
                mxx=max(mxx,mx[j]);
            }
            _new.pb({a,b,max(mxx,f[c][c]+1)});
            _new.pb({b,c,max(mxx,f[a][a]+1)});
            _new.pb({a,c,max(mxx,f[b][b]+1)});//以上是第二种转移
            if(a==b||a==c||b==c){//第一种转移
                if(b==c)
                    swap(a,b);
                if(a==c)
                    swap(b,c);
                for(int j=1;j<=n;j++)
                    _new.pb({j,c,f[a][j]+1});
            }
            for(hhh x:_new){
                f[x.u][x.v]=f[x.v][x.u]=max(f[x.u][x.v],x.w);
                mx[x.u]=max(mx[x.u],x.w);
                mx[x.v]=max(mx[x.v],x.w);
            }
            clr(_new);
        }
    }
    int ans=f[t[3*n]][t[3*n]]+1;//最后两个可能会再造成一次贡献
    for(int i=1;i<=n;i++)
        ans=max(ans,mx[i]);
    print(ans+d),pc('\n');
    return 0;
}