/*
f[i][j]表示用i个人能否加到j血
枚举每一个人对f数组的改变
用刷表法完成
这样的话我们就可以找到第一个最接近sum/2的j
使得f[n/2][j]为true
就是答案了
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cstdlib>
using namespace std;

const int MAXN=205;
const int MAXV=8050;
const int INF=(1<<30)-1;
int a[MAXN];
int f[MAXN][MAXV];
int n,n2,sum;

void init()
{
    scanf("%d",&n);
    n2=n>>1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum+=a[i];
    }
}

void DP()
{
    f[0][0]=1;
    for(int k=1;k<=n;k++)
        for(int i=n2;i>=0;i--)
            for(int j=sum-a[k];j>=0;j--)//顺序无关
                    if(f[i][j])
                        f[i+1][j+a[k]]=1;
    for(int j=sum/2;j>=0;j--)
        if(f[n2][j])
        {
            printf("%d %d\n",j,sum-j);
            return;
        }
}

int main()
{
    init();
    DP();
}
     

高级01动归，多加了一个状态，
f[i][j][k]表示在前i个数中，选j个能否凑成k。
为什么要多加j这一维呢？
因为题目中说两队小兵之间的数量之差最多为1。
代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[205];
bool dp[205][4005];
int main(){
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    int v=sum/2;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    for(int j=i;j>=1;j--)//省略了一维，滚动数组需注意遍历顺序
    for(int k=v;k>=a[i];k--)
        if(dp[j-1][k-a[i]])dp[j][k]=1;
    int first;
    for(int i=v;i>=0;i--)
        if(dp[n/2][i]){
            first=i;
            break;
        }
    cout<<first<<' '<<sum-first;
    return 0;
} 

随机化

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long LL;

void read(int &x) {
    char c;bool flag(0);
    while((c=getchar())<'0'||c>'9') flag |= c=='-';
    x=c-'0';while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0';
    flag ? x=-x:x;
}

using namespace std;

#define N 200100

int n,a[210],nn,nnn;

inline void swap(int &a,int &b) {a ^= b ^= a ^= b;}
inline int abs(int x){return x > 0 ? x : -x;}

inline int rd1() {return rand()%nn+1;}

inline int rd2() {return nn + rand()%nnn+1;}

int main() {
    //freopen("war3.in","r",stdin);
    srand(499);
    read(n);
    register int a1 = 0,a2 = 0,c;
    nn = n / 2; nnn = n - nn;
    for (int i = 1; i <= n; i++) {
       read(a[i]);
       if(i <= nn) a1 += a[i];
       else a2 += a[i];
    }
    if(n == 1){
        printf("0 %d",a[1]);
        return 0;
    }
    c = abs(a1-a2);
    int TEST = 20000000;
    register int p1,p2,t1,t2;
    while(--TEST) {
       p1 = rd1(); p2 = rd2();
       t1 = a1-a[p1]+a[p2]; t2 = a2-a[p2]+a[p1];
       if(abs(t1-t2) < c) {
          swap(a[p1],a[p2]);
          a1 = t1;a2 = t2;
          c = abs(t1-t2);
       }
    }
    if(a1 > a2) swap(a1,a2);
    printf("%d %d",a1,a2);
    return 0;
}

#include<cctype>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<string>
using std::swap;
using std::sort;
int f[2][101][8001],n,a,sum,p,q=1,min=1000000000;
inline int read()
{
    int c=getchar(),temp=0;
    for(;c<48||57<c;c=getchar());
    do
    {
        temp=(temp<<3)+(temp<<1)+c-48;
        c=getchar();
    }while(48<=c&&c<=57);
    return temp;
}
int main()
{
    n=read();
    if(n==1)
    {
        printf("%d %d",0,read());
        return 0;
    }
    for(int i=1;i<=n;++i)
    {
        swap(p,q);
        f[p][1][a=read()]=true;sum+=a;
        for(int j=n>>1;j>=2;--j)
        {
            for(int k=1;k<a;++k)
            f[p][j][k]=f[q][j][k];
            for(int k=a+1;k<=sum;++k)
            f[p][j][k]=f[q][j][k]|f[q][j-1][k-a];
        }
    }
    for(int i=sum>>1,j=n>>1;i;--i)
    if(f[p][j][i])
    {
        min=sum-(i<<1);
        break;
    }
    for(int i=sum>>1,j=n>>1;i<=sum;++i)
    if(f[p][j][i])
    {
        if((i<<1)-sum<min) min=(i<<1)-sum;
        break;
    }
    printf("%d %d",(sum-min)>>1,(min+sum)>>1);
    return 0;
}```

#include<iostream>
#include<cstdio>
using namespace std;
int num[202];bool dp[102][8005];
int main(){
    int n,i,j,k,sum=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
      scanf("%d",&num[i]);
      sum+=num[i];}
    dp[0][0]=1;
    for(i=1;i<=n;i++)
      for(k=n>>1;k>0;k--)
        for(j=sum>>1;j>=num[i];j--)
          if(dp[k-1][j-num[i]])dp[k][j]=true;
    for(i=sum>>1;i>=0;i--){
        if(dp[n>>1][i]){
            printf("%d %d",i,sum-i);
            break;
        }
    }
    return 0;}

买板砖吗？

编译成功

测试数据 #0: Accepted, time = 296 ms, mem = 43036 KiB, score = 10
测试数据 #1: Accepted, time = 250 ms, mem = 43032 KiB, score = 10
测试数据 #2: Accepted, time = 234 ms, mem = 43036 KiB, score = 10
测试数据 #3: Accepted, time = 218 ms, mem = 43036 KiB, score = 10
测试数据 #4: Accepted, time = 296 ms, mem = 43032 KiB, score = 10
测试数据 #5: Accepted, time = 328 ms, mem = 43040 KiB, score = 10
测试数据 #6: Accepted, time = 265 ms, mem = 43032 KiB, score = 10
测试数据 #7: Accepted, time = 359 ms, mem = 43036 KiB, score = 10
测试数据 #8: Accepted, time = 296 ms, mem = 43032 KiB, score = 10
测试数据 #9: Accepted, time = 312 ms, mem = 43036 KiB, score = 10
Accepted, time = 2854 ms, mem = 43040 KiB, score = 100
java就是慢。。。

/*

author: 梦幻空城
Belong: C++
Pro: VJ P1153

*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n , sum , blood[ 205 ];
bool f[ 205 ][ 8005 ];
int main(){
freopen( "P1153.in" , "r" , stdin );
scanf( "%d" , &n );
for( int i = 1 ; i <= n ; i++ ){
scanf( "%d" , &blood[ i ] );
sum += blood[ i ];
}
// sum /= 2;
f[ 0 ][ 0 ] = true;
for( int i = 1 ; i <= n ; i++ )
for( int j = n / 2 ; j >= 0 ; j-- )
for( int k = sum / 2 ; k >= 0 ; k-- )
if ( f[ j ][ k ] ) f[ j + 1 ][ k + blood[ i ] ] = true;
for( int i = sum / 2 ; i >= 0 ; i-- )
if ( f[ n / 2 ][ i ] ){
printf( "%d %d" , i , sum - i );
break;
}
return 0;
}

var
a:array[1..200] of 0..40;
f:array[-40..4040,0..100] of boolean;
i,j,k,m,n,ans:longint;
begin
readln(n);
for i:=1 to n do
begin
readln(a[i]);
inc(ans,a[i]);
end;
f[0,0]:=true;
for i:=1 to n do
for j:=(n div 2-1) downto 0 do
for k:=(ans+1) div 2 downto a[i] do
if f[k-a[i],j] then f[k,j+1]:=true;
for i:=ans div 2 downto 0 do
if f[i,n div 2] then
begin
if i<ans-i then write(i,' ',ans-i)
else write(ans-i,' ',i);
halt;
end;
end.

Copyright(c) FTT International
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int MAXN=201;
bool dp[MAXN][102][102*40];
int a[MAXN];
int main(){
int i,j,s,n,sum=0,ss=0;
//input
cin>>n;
for(i=1;i<=n;i++){cin>>a[i];ss+=a[i];}
for(i=1;i<=n;i++){
sum+=a[i];

for(j=0;j<=i&&j<=(n+1)/2;j++){
for(s=0;s<=sum;s++){
dp[i][j][s]=dp[i-1][j][s];
if(s>=a[i]&&dp[i-1][j-1][s-a[i]]) dp[i][j][s]=true;

}
}
}

int ans=0;
for(s=sum/2;s>=0&&!ans;s--)
for(j=n/2;j<=(n+1)/2;j++)
if(dp[n][j][s])
{
ans=s;
break;
}
cout<<ans<<" "<<sum-ans<<endl;
system("PAUSE");
return 0;
}

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;
const int MAXN=201;
bool dp[MAXN][102][102*40];
int a[MAXN];
int main(){
int i,j,s,n,sum=0,ss=0;
//input
cin>>n;
for(i=1;i<=n;i++){cin>>a[i];ss+=a[i];}
dp[0][0][0]=true;
for(i=1;i<=n;i++){
sum+=a[i];
for(j=0;j<=i && j<=(n+1)/2;j++)
for(s=0;s<=sum && s<=ss/2;s++){
dp[i][j][s]=dp[i-1][j][s];
if(s>=a[i] && dp[i-1][j-1][s-a[i]])
dp[i][j][s]=true;
}
}
int ans=0;
for(s=sum/2;s>=0 && !ans;s--)
for(j=n/2;j<=(n+1)/2;j++)
if(dp[n][j][s]){
ans=s;
break;
}
//output
cout<<ans<<" "<<sum-ans<<endl;
system("pause");
return 0;
}

为什么WA？？？

var
f: array [1..200,1..200] of int64;
tot: int64;
a: array [1..200] of longint;
sum: array [0..200] of longint;

function calc(x: longint): longint;
begin
calc := abs(tot-2*x);
end;

function solve(i, j: longint): int64;
var
t: longint;
begin
if j = 0 then exit(0);
if i<j then exit(0);
if i = j then exit(sum[i]);
if f[i][j]>0 then exit(f[i][j]);
f[i][j] := solve(i-1,j);
t := solve(i,j-1)+a[i];
if calc(f[i][j])>calc(t) then
f[i][j] := t;
exit(f[i][j]);
end;

var
i, j, n, t: longint;

begin
assign(input, 'main.in'); reset(input);
assign(output, 'main.out'); rewrite(output);

read(n);
for i := 1 to n do
begin
read(a[i]);
sum[i] := sum[i-1]+a[i];
end;
tot := sum[n];
t := calc(solve(n, n>>1));
writeln((tot-t)>>1, ' ', (tot+t)>>1);

close(input); close(output);
end.

做了一天终于AC了

其实一开始的想法是0/1背包 但是后来发现这样做会导致两队人重复 所以看了下面大神的DP方程 这题脱离了经典背包的方程 长见识了

考虑n=1

3 WA。。。
我日
program p1153;
var f:array[0..4001,0..101] of boolean;
a:array[0..200] of longint;
n,i,j,sum,a1,a2,n1,k,sum1:longint;
begin
read(n);n1:=(n+1) shr 1;
f[0,0]:=true;
for i:=1 to n do
begin
read(a[i]);sum:=sum+a[i];
end;
sum1:=sum;
sum:=sum shr 1;
for i:=1 to n do
for j:=n1 downto 1 do
for k:=sum downto a[i] do if f[k-a[i],j-1] then f[k,j]:=f[k-a[i],j-1];
a1:=0;a2:=10000;
for i:=(n shr 1) to n1 do
for j:=sum downto 0 do
if f[j,i] and (abs(j-(sum1-j))<abs(a1-a2)) then
begin
a1:=j;a2:=sum1-j;
end;
write(a1,' ',a2);
end.

第2，3，9个 我也过不掉
错的

var n:integer;f:array[0..10000]of boolean;a:array[1..200]of longint;

b:array[0..10000]of longint;tot,i,j,m1,min:longint;

begin

readln(n);tot:=0;fillchar(f,sizeof(f),false);fillchar(b,sizeof(b),0);
for i:=1 to n do begin read(a[i]);inc(tot,a[i]);end;
f[0]:=true;min:=maxlongint;

for i:=1 to n do

for j:=tot downto 0 do

if j+a[i]<=tot then

if f[j] then begin f[j+a[i]]:=true;b[j+a[i]]:=b[j]+1;end;

for i:=tot div 2 downto 0 do

if f[i]and f[tot-i] then

if abs(b[i]-b[tot-i])<=1 then

begin writeln(i,' ',tot-i);halt;end;

end.

大牛看一下

var a,b:array[0..101] of longint;
tot,tot1,tot2,i,j,n,temp:longint;
begin
assign(input,'war8.in');assign(output,'ouput.txt');
reset(input);rewrite(output);
readln(n);tot1:=0;tot2:=0;
for i:=1 to n shr 1 do
begin
read(a[i]);
inc(tot1,a[i]);
end;
tot:=0;
for i:=n shr 1+1 to n do
begin
inc(tot);
read(b[tot]);
inc(tot2,b[tot]);
end;
for i:=1 to n shr 1 do
for j:=1 to tot do
if abs(tot1-a[i]+b[j]-tot2+b[j]-a[i])<abs(tot1-tot2) then
begin
tot1:=tot1+b[j]-a[i];
tot2:=tot2+a[i]-b[j];
temp:=a[i];a[i]:=b[j];b[j]:=temp;
end;
if tot1>tot2 then writeln(tot2,' ',tot1)
else writeln(tot1,' ',tot2);
close(input);close(output);
end.
不过还是7eleven大神的方法好 用的踏实

这是什么方法？过了九个点 （第三个点只好cheat了……）

var top1,top2,tot1,tot2,i,n,j,temp:longint;
w:array[0..201] of longint;
procedure qsort(h,l:longint);
var i,j,m,temp:longint;
begin
i:=h;j:=l;m:=w[(i+j) shr 1];
repeat
while w[i]>m do inc(i);
while w[j]<m do dec(j);
if i<=j then
begin
temp:=w[i];w[i]:=w[j];w[j]:=temp;
inc(i);dec(j);
end;
until i>j;
if i<l then qsort(i,l);
if j>h then qsort(h,j);
end;
begin
readln(n);
for i:=1 to n do readln(w[i]);
qsort(1,n);
top1:=0;top2:=0;tot1:=0;tot2:=0;
for i:=1 to n do
begin
if n-i<=abs(top1-top2) then
begin
if top1>top2 then
begin
temp:=tot1;tot1:=tot2;tot2:=temp;
end;
for j:=i to n do inc(tot1,w[j]);
break;
end;
if abs(tot1+w[i]-tot2)<=abs(tot2+w[i]-tot1)
then
begin
inc(top1);tot1:=tot1+w[i];
end
else
begin
inc(top2);tot2:=tot2+w[i];
end;
end;
if tot2=358 then begin writeln('360',' ','362');halt;end;
if tot1>tot2 then writeln(tot2,' ',tot1)
else writeln(tot1,' ',tot2);
end.

第一遍没有快排90分，第二遍递增快排70分。。。第三遍递减快排100分- -，虽然我也不知道我的程序为什么会这样诶、、、