wa了7,10两个测试点,我本地下载第7个测试点,输出答案完全正确,为什么wa?
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
const int N=2e3+6,yyx=1e4+7;
int n,m,a[N],b[N],pre[N],dp[N][N*10],v[N][N*10];
void solve(){
cin>>n;
int res=0,sum=0;
for(int i=1;i<=n;++i){
int x,y;cin>>x>>y;
a[i]=x-y;
if(a[i]>0) b[i]=1,sum+=a[i];
if(a[i]<0) b[i]=-1,sum-=a[i],res++;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=sum;++j){
dp[i][j]=dp[i-1][j];
v[i][j]=v[i-1][j];
if(j==2*abs(a[i])||v[i-1][j-2*abs(a[i])]){
if(!v[i][j]){
dp[i][j]=dp[i-1][j-2*abs(a[i])]+b[i];v[i][j]=1;
}
else{
dp[i][j]=min(dp[i][j],dp[i-1][j-2*abs(a[i])]+b[i]);
}
}
}
}
int cnt=0;
for(int i=sum;i;--i){
if(v[n][i]){
cnt=i;break;
}
}
cout<<res+dp[n][cnt]<<endl;
}
signed main(){
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}
附第七个测试点
输入: 200
1 6 1 5 1 1 2 5 5 3 1 6 1 5 1 6 1 2 1 5 1 3 4 1 1 6 4 5 1 3 1 6 5 6 2 5 5 6 1 5 1 4 1 6 6 2 1 5 6 1 2 3 3 4 2 3 1 2 3 5 2 5 1 5 4 6 1 6 2 4 1 4 1 4 1 5 2 4 6 1 2 6 1 4 3 6 5 6 1 5 1 6 1 5 1 6 2 5 1 6 1 6 1 3 6 1 4 6 1 6 4 6 1 1 1 3 3 6 1 6 3 5 1 3 1 6 3 5 4 5 1 5 1 6 3 6 1 4 1 1 1 2 1 2 5 2 1 6 4 6 1 5 5 6 1 6 5 6 2 3 1 6 1 5 1 5 1 6 2 1 1 5 1 2 1 5 1 6 3 1 1 6 4 5 1 5 1 3 1 6 2 6 1 3 1 6 1 4 1 5 1 3 1 6 1 4 4 1 3 5 1 5 1 4 1 5 2 5 1 5 1 4 2 4 2 4 1 4 1 6 5 1 1 6 2 6 1 5 2 5 1 6 3 6 1 6 6 5 2 5 1 5 1 6 1 3 1 6 2 6 1 6 1 6 2 1 1 6 1 5 4 5 1 5 2 4 2 6 1 4 1 6 3 6 4 6 1 6 1 5 1 2 1 5 1 6 1 3 2 5 5 6 1 5 5 6 1 5 3 5 3 5 4 1 2 4 1 6 1 6 1 2 2 5 2 1 5 6 2 3 2 5 1 6 1 5 2 3 2 6 1 3 1 6 6 1 2 4 1 6 1 6 1 3 2 3 4 5 3 5 2 4 1 6 1 3 2 6 1 5 1 3 5 6 3 4 2 5 1 5 2 6 2 5 5 6 1 4 4 6 1 6 1 6 4 6 1 6 1 6 输出:55