自动搬运

查看原文

来自洛谷，原作者为

	ETHANK 「我是星 我愿投身前途未卜的群星，为梦长明。」

搬运于2025-08-24 22:34:54，当前版本为作者最后更新于2021-12-26 06:51:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目难度：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$ 必须满足如下条件之一：

• 牛 $k$ 的品种是 $H$
• 牛 $k$ 与当前牛的距离大于 $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]));