「USACO21DEC」Paired Up P

First of all, Holstein cattle and gensai cattle are separated and sorted from small to large.

Consider the subtask with T=1 ＾.

It's easy to think of \ (f_{i,j} \) as the maximum weight and weight of the paired cows that can be obtained after the first \ (I \) Holstein cattle and the first \ (j \) gengsai cattle are matched.

The answer is \ (\ sum {I = 1} ^ {n} y _i-f {cnt1, cnt2} \), where \ (cnt1 \) represents the number of Holstein cattle and \ (cnt2 \) represents the number of more racing cattle.

Define the check(i,j) function to judge whether the \ (i \) Holstein cow and gengsai cow can match.

The transfer code is as follows:

for(int i=1;i<=cnt1;++i)
{
	for(int j=1;j<=cnt2;++j)
	{
		f[i][j]=max(f[i-1][j],f[i][j-1]);
		if(check(i,j)) f[i][j]=max(f[i][j],f[i-1][j-1]+A[i].y+B[j].y);
	}
}

So we'll find a problem. Maybe the optimal solution matches like this.

That is \ (1,4 \) matching and \ (2,3 \) matching.

In this case, we cannot transfer in this way, but it is easy to find that since \ (2,3 \) can match and \ (1,4 \) can match, \ (2,4 \) must match, and similarly \ (1,3 \) must match.

Therefore, the matching of \ (1,3 \) and \ (2,4 \) will be transferred in dp, and the two cases are equivalent.

So our transfer formula is correct.

Consider subtasks with T= 2

Because the pairing is great, when we want a cow to account for the contribution of the answer, we must make sure that there is no cow that can be paired with it in the pairing range of this cow.

Continue to consider that \ (f_{i,j} \) represents the maximum weight sum of unmatched cows formed by the first \ (I \) Holstein and \ (j \) gengsai cattle.

Note that this state does not tell us whether we can make a cow count the unpaired contribution, so open one dimension more.

Use \ (f_{i,j,0/1} \) to indicate that the first \ (I \) Holstein cattle and \ (j \) gengsai cattle have been processed, and the next Holstein cattle / gengsai cattle can be included in the contribution.

So there

How to transfer between \ (f {I, J, 0} \) and \ (f {I, J, 1} \)?

\(f_{i,j,0} \) indicates that only Holstein cattle can be transferred, indicating that the (i \) Holstein cattle may not be matched, so we need to find the previous position \ (j+len \) of the first more racing cattle that cannot be paired with the (i \) Holstein cattle. If both \ (i+1 \) to \ (i+len \) and \ (j+1 \) to \ (j+len \) can be matched, Then \ (f {i, J, 0} \) can be transferred to \ (f {i+len, j+len, 1} \).

Similarly \ (f {I, J, 1} \) can also be transferred to \ (f {I + len, j + len, 0} \) under corresponding conditions.

If the \ (i \) Holstein cow of \ (f {i, J, 0} \) is matched, the above transfer will be wrong, but in fact, the optimal solution in this case will be transferred by the formula \ (f {i, J, 0 / 1} \ rightarrow f {i, J, 0 / 1} \).

The code is as follows:

memset(dp,-0x3f,sizeof dp);
		dp[0][0][0]=dp[0][0][1]=0;
		for(int i=cnt1;i>=1;--i)
		{
			for(int j=cnt2;j>=1;--j)
			{
				if(check(i,j)) match[i][j]=match[i+1][j+1]+1;
				else match[i][j]=0;
			}
		}
		for(int i=1,j=1;i<=cnt1;++i)
		{
			while(j<=cnt2&&(check(i,j)||B[j].x<A[i].x)) ++j;
			nxtH[i]=j;
		}
		for(int i=1,j=1;i<=cnt2;++i)
		{
			while(j<=cnt1&&(check(j,i)||A[j].x<B[i].x)) ++j;
			nxtG[i]=j;
		}
		nxtH[0]=nxtG[0]=1;
		for(int i=0;i<=cnt1;++i)
		{
			for(int j=0;j<=cnt2;++j)
			{
				int step=max(nxtH[i]-j-1,0);
				if(i+step<=cnt1&&match[i+1][j+1]>=step)
					dp[i+step][j+step][1]=max(dp[i+step][j+step][1],dp[i][j][0]);
				step=max(nxtG[j]-i-1,0);
				if(j+step<=cnt2&&match[i+1][j+1]>=step)
					dp[i+step][j+step][0]=max(dp[i+step][j+step][0],dp[i][j][1]);
				if(i<cnt1&&j<cnt2&&check(i+1,j+1))
				{
					dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j][0]);
					dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j][1]);
				}
				if(i<cnt1) dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+A[i+1].y);
				if(j<cnt2) dp[i][j+1][1]=max(dp[i][j+1][1],dp[i][j][1]+B[j+1].y);
			}
		}

All codes are as follows:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e3+5;
int T,n,K,cnt1,cnt2;
char ty[MAXN][4];
int f[MAXN][MAXN],X[MAXN],Y[MAXN],dp[MAXN][MAXN][2];
int nxtH[MAXN],nxtG[MAXN],match[MAXN][MAXN];
struct COW
{
	int x,y;
}A[MAXN],B[MAXN];
bool check(int i,int j)
{
	if(abs(A[i].x-B[j].x)<=K) return true;
	return false;
}
int main()
{
	int testsum=0;
	scanf("%d %d %d",&T,&n,&K);
	for(int i=1;i<=n;++i)
		scanf("%s %d %d",ty[i]+1,&X[i],&Y[i]),testsum+=Y[i];
	for(int i=1;i<=n;++i)
	{
		if(ty[i][1]=='G') A[++cnt1]=COW{X[i],Y[i]};
		else B[++cnt2]=COW{X[i],Y[i]};
	}
	if(T==1)
	{
		for(int i=1;i<=cnt1;++i)
		{
			for(int j=1;j<=cnt2;++j)
			{
				f[i][j]=max(f[i-1][j],f[i][j-1]);
				if(check(i,j)) f[i][j]=max(f[i][j],f[i-1][j-1]+A[i].y+B[j].y);
			}
		}
		int sum=-f[cnt1][cnt2];
		for(int i=1;i<=n;++i) sum+=Y[i];
		printf("%d\n",sum);
	}
	else
	{
		memset(dp,-0x3f,sizeof dp);
		dp[0][0][0]=dp[0][0][1]=0;
		for(int i=cnt1;i>=1;--i)
		{
			for(int j=cnt2;j>=1;--j)
			{
				if(check(i,j)) match[i][j]=match[i+1][j+1]+1;
				else match[i][j]=0;
			}
		}
		for(int i=1,j=1;i<=cnt1;++i)
		{
			while(j<=cnt2&&(check(i,j)||B[j].x<A[i].x)) ++j;
			nxtH[i]=j;
		}
		for(int i=1,j=1;i<=cnt2;++i)
		{
			while(j<=cnt1&&(check(j,i)||A[j].x<B[i].x)) ++j;
			nxtG[i]=j;
		}
		nxtH[0]=nxtG[0]=1;
		for(int i=0;i<=cnt1;++i)
		{
			for(int j=0;j<=cnt2;++j)
			{
				int step=max(nxtH[i]-j-1,0);
				if(i+step<=cnt1&&match[i+1][j+1]>=step)
					dp[i+step][j+step][1]=max(dp[i+step][j+step][1],dp[i][j][0]);
				step=max(nxtG[j]-i-1,0);
				if(j+step<=cnt2&&match[i+1][j+1]>=step)
					dp[i+step][j+step][0]=max(dp[i+step][j+step][0],dp[i][j][1]);
				if(i<cnt1&&j<cnt2&&check(i+1,j+1))
				{
					dp[i+1][j+1][0]=max(dp[i+1][j+1][0],dp[i][j][0]);
					dp[i+1][j+1][1]=max(dp[i+1][j+1][1],dp[i][j][1]);
				}
				if(i<cnt1) dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][0]+A[i+1].y);
				if(j<cnt2) dp[i][j+1][1]=max(dp[i][j+1][1],dp[i][j][1]+B[j+1].y);
			}
		}
		printf("%d\n",max(dp[cnt1][cnt2][0],dp[cnt1][cnt2][1]));
	}
	return 0;
}