nbu 2414 Please help the poor donkey! - c++编程基础

urn a>b a:b;}
template T _abs(T a){return a>0 a:-a;}
template T _mod(T a,T m){return a template T _gcd(T a,T b){while(b){T t=b;b=a%b;a=t;}return a;}
template void _swap(T &a,T &b){T t=b;b=a;a=t;}
template void getmax(T &a,T b){a= a>b a:b;}
template void getmin(T &a,T b){a= (a!=-1 && a int TS,cas=1;
const int M=1000+5;
int n,m,w[M],dp[2][M*20];
int lsum,rsum,sum;

void run(){
int i,j;
m+=n,lsum=rsum=0;
for(i=1;i<=n;i++){
scanf("%d",&w[i]);
lsum+=w[i];
}
for(;i<=m;i++){
scanf("%d",&w[i]);
rsum+=w[i];
}
sum=lsum+rsum;
int now=0,pre=1;
clr_all(dp,-1);
dp[now][lsum]=0;
for(i=1;i<=m;i++){
pre=now,now^=1;
for(j=0;j<=sum;j++) dp[now][j]=dp[pre][j];
for(j=0;j<=sum;j++) if(dp[pre][j]!=-1){
if(i>n) getmin(dp[now][j+w[i]],dp[pre][j]+1);
else getmin(dp[now][j-w[i]],dp[pre][j]+1);
}
}
for(i=sum/2+1;i<=sum;i++) if(dp[now][i]!=-1) break;
for(j=sum/2;j>=0;j--) if(dp[now][j]!=-1) break;
int r;
if(dp[now][i]==-1) r=j;
else if(dp[now][j]==-1) r=i;
else{
if(_abs(sum-i-i) == _abs(sum-j-j))
r= dp[now][i] else
r= _abs(sum-i-i)<_abs(sum-j-j) i:j;
}
printf("%d\n",dp[now][r]);
}

void presof(){
}

int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
presof();
//run();
while(~scanf("%d%d",&n,&m)) run();
//for(scanf("%d",&TS),cas=1;cas<=TS;cas++) run();
return 0;
}

nbu 2414 Please help the poor donkey! (二)