rt 贴一份luogu AC代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define N 6005
using namespace std;
int INF = 0x3f3f3f3f;
int a[1005],b[1005];
int dp[1005][13010];
int n,ans;
bool check(int x)
{
	return x>=-N && x<=N;
}
int main()
{
	memset(dp,0x3f,sizeof dp);
    scanf("%d",&n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d%d",&a[i],&b[i]);
    }
    dp[0][N]=0;
    for(int i = 1;i <= n;i++)
    {
		int dis = a[i]-b[i];
        for(int j = -N;j <= N;j++)
		{
			if(check(j-dis))
			{
				dp[i][j+N] = min(dp[i][j+N],dp[i-1][j-dis+N]);
			}
			if(check(j+dis))
			{
				dp[i][j+N] = min(dp[i][j+N],dp[i-1][j+dis+N]+1);
			}
		}
    }
    for(int i = 0;i <= N;i++)
    {
        if(dp[n][i+N]!=INF || dp[n][N-i]!=INF)
		{
			cout << min(dp[n][i+N], dp[n][N-i]);
			break;
		}
    }
    return 0;
}