胜者组题解

良心WA题人 · 2024-01-12 15:54:47 · 题解

首先发现每种小团体独立。

对于每一个小团体，将选出来的两个学生看成线段的左右端点后，任意两对学生不会相交。因为若两对学生 (pl,pr) 和 (ql,qr) 满足 p_l\le q_l\le p_r\le q_r，则选出 (p_l,q_l) 和 (p_r,q_r) 显然更优（将贡献写出来后读者自证不难）。

我们将贡献拆开变成 a_i-x\times i+a_j+x\times j。于是对于每个小团体 dp 算出 f_{i,j,0/1} 表示该小团体前 i 个点用 j 次信息学名额，当前是完整匹配/剩余了一个待匹配点的最小不满值。

具体的，f_{i,j,0}=\min(f_{i-1,j-1,0},f_{i-1,j,1}+a_i+x\times i) 表示当前点不选花费一次名额则直接继承，或者当前点用待匹配的一半匹配上。同理，f_{i,j,1}=\min(f_{i-1,j-1,1},f_{i-1,j,0}+a_i-x\times i)。

然后考虑在外面使用背包。令 g_{i,j} 表示考虑前 i 个小团体用 j 个名额的最小不满值。直接分组背包即可。因为所有颜色的个数和为 n，所以背包合并的时间复杂度为 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN=5004;
vector<int>t[NN];
int a[NN],c[NN];
ll f[NN][NN][2],g[NN][NN];
int main()
{
    int n,m,d,x;
    scanf("%d%d%d%d",&n,&m,&d,&x);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        t[c[i]].push_back(i);
    }
    memset(g,0x3f,sizeof(g));
    g[0][0]=0;
    int cnt=0;
    for(int i=1;i<=d;i++)
    {
        for(int j=0;j<=t[i].size();j++)
            for(int k=0;k<=m;k++)
                f[j][k][0]=f[j][k][1]=1e18;
        f[0][0][0]=0;
        for(int j=1;j<=t[i].size();j++)
            for(int k=0;k<=m;k++)
            {
                f[j][k][0]=f[j-1][k][1]+a[t[i][j-1]]+1ll*x*t[i][j-1];
                f[j][k][1]=f[j-1][k][0]+a[t[i][j-1]]-1ll*x*t[i][j-1];
                if(k)
                {
                    f[j][k][0]=min(f[j][k][0],f[j-1][k-1][0]);
                    f[j][k][1]=min(f[j][k][1],f[j-1][k-1][1]);
                }
            }
        for(int j=0;j<=cnt;j++)
            for(int k=0;k<=t[i].size();k++)
                if(j+k<=m)
                    g[i][j+k]=min(g[i][j+k],g[i-1][j]+f[t[i].size()][k][0]);
        cnt+=t[i].size();
    }
    ll ans=1e18;
    for(int i=0;i<=m;i++)
        ans=min(ans,g[d][i]);
    if(ans>9e17)
    {
        printf("Impossible");
        return 0;
    }
    printf("%lld",ans);
    return 0;
}