[ARC142F] Paired Wizards

syzf2222 · 2022-11-08 15:27:09 · 题解

这题提醒我们更多去关注条件的性质。

如果条件性质不多，可以用分类讨论创造性质。

首先可以做一步转化，假设所有使用 2 的时间和为 T，X 使用了 C_X 次 2，Y 使用了 C_Y 次，则答案为 T-\frac{C_X(C_X+1)}{2}-\frac{C_Y(C_Y+1)}{2}。

开始分讨：

• \{(a_i,b_i),(c_i,d_i)\}=\{(1,2),(2,1)\}
• \{(a_i,b_i),(c_i,d_i)\}=\{(1,1),(2,2)\}

显然第 3,4 种情况都是会取一个后缀。

我们可以枚举第二种的划分情况，然后预处理一些后缀情况就好。

具体的我们可以预处理 f_i 表示 X 已有 i 个然后 4 情况中如何选最优，类似对 Y 定义 g_i。然后我们枚举划分情况，枚举 3 情况的后缀，结合 f,g 可以算出答案。详见代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
const int mod=1e9+7;
#define inf 1e9
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
const int N=8005;
int n,m,tp[N],Ans,Sum,X,Y,cnt,f[N],g[N];
int main(){
    n=read();
    for(int i=1,a,b,c,d;i<=n;i++){
        a=read(),b=read(),c=read(),d=read();
        if(a==c&&b==d){
            if(a==2)Sum+=i,++X;
            if(b==2)Sum+=i,++Y;
        }else if(a==c){
            if(a==2)Sum+=i,++X;
            tp[i]=2;
        }else if(b==d){
            if(b==2)Sum+=i,++Y;
            tp[i]=1;
        }else if(a==b)tp[i]=3;
        else ++cnt,Sum+=i;
    }
    for(int i=0;i<=n;i++){
        f[i]=g[i]=-i*(i+1)/2;
        for(int j=n,a=i,b=f[i];j;--j)
            if(tp[j]==1)++a,b+=j-a,f[i]=max(f[i],b);
        for(int j=n,a=i,b=g[i];j;--j)
            if(tp[j]==2)++a,b+=j-a,g[i]=max(g[i],b);
    }Ans=-inf;
    for(int i=0;i<=cnt;i++){
        Ans=max(Ans,f[X+i]+g[Y+cnt-i]);
        for(int j=n,a=0,b=0;j;--j)if(tp[j]==3)
            ++a,b+=j+j,Ans=max(Ans,f[X+i+a]+g[Y+cnt-i+a]+b);
    }printf("%d\n",Ans+Sum);
    return 0;
}

深深地感到自己的弱小。