91分求助,wa10,已经考虑到+-
查看原帖
91分求助,wa10,已经考虑到+-
714900
zyzbldnb楼主2023/2/10 22:45

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;
}
2023/2/10 22:45
加载中...