抄tj的CE 题目传送门 此题思路:多状态DP 代码:

#include<bits/stdc++.h>
using namespace std;
int n,f[5000][5000],a[10100000],b[10100000];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
	for(int i=0;i<=n;i++)
		for(int j=0;j<2000;j++)
			f[i][j]=INT_MAX;
	f[0][1000]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<2000;j++)
			if(f[i-1][j]!=INT_MAX)
			{
				int x=a[i]-b[i];
				if(j+x>=0&&j+x<2000) f[i][j+x]=min(f[i][j+x],f[i-1][j]);
				if(j-x>=0&&j-x<2000) f[i][j-x]=min(f[i][j-x],f[i-1][j]+1);
			}
	int minf=INT_MAX;
	for(int i=0;i<=1000;i++)
	{
		if(f[n][1000+i]!=INT_MAX) minf=min(minf,f[n][1000+i]);
		if(f[n][1000-i]!=INT_MAX) minf=min(minf,f[n][1000-i]);
		if(minf!=INT_MAX)
		{
			cout<<minf;
			return 0;
		}
	}
}

#include<bits/stdc++.h>
using namespace std;
int n;
struct node{
	int a,b;
}a[1010];
int ans;
int dp[1010][6010][2];
bool f[1010][6010][2];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i].a>>a[i].b;
	memset(f,0,sizeof(f));
	memset(dp,127,sizeof(dp));
	f[0][0][0]=1;
	dp[0][0][0]=0;
	f[0][0][1]=1;
	dp[0][0][1]=0;
	for(int i=1;i<=n;i++){
		for(int j=-6000;j<=6000;j++){
			int x1,x2;
			x1=j-(a[i].a-a[i].b),x2=j-(a[i].b-a[i].a);
			if(x1>=0){
				int y1=abs(x1);
				if(j>=0){
					if(f[i-1][y1][0])dp[i][abs(j)][0]=min(dp[i][abs(j)][0],dp[i-1][y1][0]),f[i][abs(j)][0]=1;
				}
				else{
					if(f[i-1][y1][0])dp[i][abs(j)][1]=min(dp[i][abs(j)][1],dp[i-1][y1][0]),f[i][abs(j)][1]=1;
				}
			}
			else{
				int y1=abs(x1);
				if(j>=0){
					if(f[i-1][y1][1])dp[i][abs(j)][0]=min(dp[i][abs(j)][0],dp[i-1][y1][1]),f[i][abs(j)][0]=1;
				}
				else{
					if(f[i-1][y1][1])dp[i][abs(j)][1]=min(dp[i][abs(j)][1],dp[i-1][y1][1]),f[i][abs(j)][1]=1;
				}
			}
			if(x2>=0){
				int y1=abs(x2);
				if(j>=0){
					if(f[i-1][y1][0])dp[i][abs(j)][0]=min(dp[i][abs(j)][0],dp[i-1][y1][0]+1),f[i][abs(j)][0]=1;
				}
				else{
					if(f[i-1][y1][0])dp[i][abs(j)][1]=min(dp[i][abs(j)][1],dp[i-1][y1][0]+1),f[i][abs(j)][1]=1;
				}
			}
			else{
				int y1=abs(x2);
				if(j>=0){
					if(f[i-1][y1][1])dp[i][abs(j)][0]=min(dp[i][abs(j)][0],dp[i-1][y1][1]+1),f[i][abs(j)][0]=1;
				}
				else{
					if(f[i-1][y1][1])dp[i][abs(j)][1]=min(dp[i][abs(j)][1],dp[i-1][y1][1]+1),f[i][abs(j)][1]=1;	
				}
			}
		}
	}
	for(int i=0;i<=6000;i++){
		if(f[n][i][1]&&f[n][i][0]){
			cout<<min(dp[n][i][1],dp[n][i][0]);
			return 0;
		}
		if(f[n][i][1]){
			cout<<dp[n][i][1];
			return 0;
		}
		if(f[n][i][0]){
			cout<<dp[n][i][0];
			return 0;
		}
	}
	return 0;
}