题解

191 条题解

  • 10
    @ 2017-05-08 12:27:11
    /*
    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();
    }
         
    
  • 2
    @ 2020-07-26 22:44:41

    高级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;
    } 
    
  • 2
    @ 2017-03-11 20:04:27

    随机化

    #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;
    }
    
  • 1
    @ 2016-06-17 11:52:32
    #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;
    }```
    
  • 0
    @ 2020-05-15 22:37:37
    #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
    @ 2016-05-06 12:17:17

    买板砖吗?

  • 0
    @ 2016-02-04 12:54:44

    编译成功

    测试数据 #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就是慢。。。

  • 0
    @ 2015-08-25 16:21:12

    /*

    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;
    }

    • @ 2016-01-12 10:21:37

      *5 1 1 1 1 12 这组数你的程序可能不对吧

  • 0
    @ 2015-07-27 16:52:40

    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.

  • 0
    @ 2015-02-03 14:32:16

    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;
    }

  • 0
    @ 2015-02-03 14:28:22

    #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;
    }

  • 0
    @ 2014-11-06 23:11:50

    为什么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.

  • 0
    @ 2014-10-21 08:03:37

    做了一天终于AC了

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

  • 0
    @ 2014-08-17 20:21:24

    考虑n=1

  • 0
    @ 2014-08-17 20:21:14

    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.

  • 0
    @ 2014-03-31 20:36:06

    第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.

    大牛看一下

  • 0
    @ 2014-03-08 20:06:37

    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大神的方法好 用的踏实

  • 0
    @ 2014-03-08 19:48:38

    这是什么方法?过了九个点 (第三个点只好cheat了……)

  • 0
    @ 2014-03-08 19:48:03

    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.

  • 0
    @ 2013-09-30 23:28:52

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

信息

ID
1153
难度
7
分类
动态规划 | 背包 点击显示
标签
递交数
4720
已通过
1026
通过率
22%
被复制
6
上传者