wa10 正解353,我353,考虑到了+-两种情况,调试发现两种情况都是353
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int f[1005][6005],a[1005],b[1005],sup[1005];// f[i][j],前i行,上行的和是j,的最小值
int main()
{
int n,sum=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
sup[i]=sup[i-1]+max(a[i],b[i]);
sum+=a[i]+b[i];
}
memset(f,0x1,sizeof(f));
f[0][0]=0;
f[1][a[1]]=0;f[1][b[1]]=1;
for(int i=2;i<=n;i++)
{
for(int j=max(b[i],a[i]);j<=sup[i];j++)
{
f[i][j]=min(f[i-1][j-a[i]],f[i-1][j-b[i]]+1);// 不翻i与翻i
}
}
int ans=6005,id=0,t=6005;
for(int i=1;i<=sup[n];i++)
{
if(f[n][i]<6005)//
{
if( abs( sum-i-i)<=ans ) //要= ,可能+,—
ans=abs(sum-i-i),t=min(t,f[n][i]);
}
}
cout<<t;//f[n][id];
return 0;
}