题解 P7985 [USACO21DEC] Paired Up P

· · 题解

题目难度：USACO P+/NOI-

子任务 1：T=1,N\le 5000

设 dp[i][j] 为当前考虑到第 i 头 H 牛，第 j 头 G 牛时匹配的牛的最大权值和。那么我们可以选择不匹配 i ，不匹配 j ，或者是将 i 和 j 匹配。

时间复杂度： O(N^2)

#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define pii pair<int,int>
#define vi vector<int>
int main(){
    T=read(),n=read(),K=read();
    vector <pii> cow[2];
    cow[0].pb({0,0}),cow[1].pb({0,0});
    rep(i,1,n){
        cin>>c;
        int x=read(),y=read();
        cow[c=='H'].pb({x,y});
        sum+=y;
    }
    A=sz(cow[0]),B=sz(cow[1]);
    if(T==1){
        vector <vi> dp(A+1,vi(B+1));
        rep(i,1,A)rep(j,1,B){
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(abs(cow[0][i].x-cow[1][j].x)<=K)
                dp[i][j]=max(dp[i][j],dp[i-1][j-1]+cow[0][i].y+cow[1][j].y);
        }
        printf("%d\n",sum-dp[A][B]);
    }
}

子任务 2：T=2,N\le 300

对于最大化未匹配的权值和，我们考虑使用类似的 dp 状态。但是注意到在上述转移时，有时候我们考虑的并不是最大匹配，只是因为最优解只产生于最大匹配（若不是最大匹配，多匹配两头牛显然更优），我们才能得到 T=1 时的答案。

于是我们需要把最大匹配这一限制加入我们的 dp 状态，具体地，我们加入一维 k 表示最后一头未匹配的牛，假设我们不想匹配当前的 H 牛，那么牛 k 必须满足如下条件之一：

状态量是 O(N^3) ，每次转移还是 O(1) 的，足够通过该子任务。

时间复杂度：O(N^3)

vector <vector<vi>> dp(A+1,vector<vi>(B+1,vi(n+1,-1)));
dp[0][0][n]=0;
rep(i,0,A)rep(j,0,B)rep(k,0,n){
    if(dp[i][j][k]==-1)continue;
    if(i<A&&j<B&&abs(cow[0][i].x-cow[1][j].x)<=K)
        Max(dp[i+1][j+1][k],dp[i][j][k]);
    if(i<A&&(!(A<=k&&k<n&&cow[0][i].x<=cow[1][k-A].x+K)))
        Max(dp[i+1][j][i],dp[i][j][k]+cow[0][i].y);
    if(j<B&&(!(k<A&&cow[1][j].x<=cow[0][k].x+K)))
        Max(dp[i][j+1][A+j],dp[i][j][k]+cow[1][j].y);
}
int ans = 0;
rep(i,0,n)Max(ans,dp[A][B][i]);
printf("%d\n",ans);

子任务 1：T=1,N\le 5000

考虑最终的优化，i,j 两维比较难舍去，但我们可以修改最后一维的定义。定义 dp[i][j][x] 为处理到前 i 头 H 牛， j 头 G 牛，并且钦定下一种不放入匹配的牛的品种为 x 。有转移：

dp[i][j][x]\to dp[i+1][j+1][x]\\ dp[i][j][H]\to dp[i+1][j][H]\\ dp[i][j][G]\to dp[i][j+1][G]\\

当然我们也可以转换钦定的品种：如果之前我们被强制不选 H 牛，那么最后一个未匹配的 H 牛最多是第 i 个。能不放入匹配的 G 牛需要离该牛距离至少为 K ，且在该牛之前的所有牛都要放入匹配。预处理出对于所有 i ，满足条件的 G 牛编号的最小值，并且判断这段区间的牛是否能全部匹配即可。

时间复杂度：O(N^2)

per(i,A,1)per(j,B,1){
    if(chk(i,j))lst[i][j]=lst[i+1][j+1]+1;
    else lst[i][j]=0;
}
int j=1;
rep(i,1,A){
    while(j<=B&&(chk(i,j)||G[j].x<H[i].x))j++;
    nxtH[i] = j;
}
j=1;
rep(i,1,B){
    while(j<=A&&(chk(j,i)||H[j].x<G[i].x))j++;
    nxtG[i] = j;
}
memset(f,-0x3f,sizeof(f));
memset(g,-0x3f,sizeof(g));
nxtG[0] = nxtH[0] = 1;
f[0][0] = g[0][0] = 0;
rep(i,0,A)rep(j,0,B){
    int cnt = max(nxtH[i]-j-1,0);
    if(i+cnt<=A && lst[i+1][j+1]>=cnt)
        Max(g[i+cnt][j+cnt],f[i][j]);
    cnt = max(nxtG[j]-i-1,0);
    if(j+cnt<=B && lst[i+1][j+1]>=cnt)
        Max(f[i+cnt][j+cnt],g[i][j]);
    if(i<A && j<B && chk(i+1,j+1)){
        Max(f[i+1][j+1],f[i][j]);
        Max(g[i+1][j+1],g[i][j]);
    }
    if(i<A) Max(f[i+1][j],f[i][j]+H[i+1].y);
    if(j<B) Max(g[i][j+1],g[i][j]+G[j+1].y);
}
printf("%d\n",max(f[A][B],g[A][B]));