为啥wa??
查看原帖
为啥wa??
1122530
elpsconr楼主2024/7/27 18:33

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

2024/7/27 18:33
加载中...