题解

239 条题解

  • 0
    @ 2010-03-11 17:15:29

    贴一个短点的..

    var f:array[0..20000]of boolean;

    i,n,maxv,v,j:longint;

    begin

    readln(maxv);

    readln(n);

    f[0]:=true;

    for i:=1 to n do

    begin

    readln(v);

    for j:=maxv downto v do if f[j-v] then f[j]:=true;

    end;

    for i:=maxv downto 1 do if f[i] then

    begin

    writeln(maxv-i);

    halt;

    end;

    end.

  • 0
    @ 2010-03-07 10:34:17

    program zhuang;

    var

    v,n,i,k:integer;

    x:array[1..10000] of integer;

    f0,f1:array[1..10000] of boolean;

    begin

    readln(v,n);

    for i:=1 to n do readln(x[i]);

    fillchar(f0,sizeof(f0),0);

    f0[0]:=true;

    for i:=1 to n do

    begin

    f1:=f0;

    if x[i]>v then continue;

    for j:=x[i] to v do

    if f0[j-x[i]] then f1[j]:=true;

    f0:=f1;

    end;

    for k:=v downto 0 do

    if f1[k] then

    begin

    writeln(v-k);

    halt;

    end;

    end.

  • 0
    @ 2009-11-18 19:33:01

    #include

    using namespace std;

    int sum=0,a[30000];

    int n,v;

    void work()

    {

    int i,j;

    cin>>v>>n;

    int maxn=0;

    for (i=1;i>i1;

    a[i1]=1;

    maxn=max(maxn,i1);

    int max1=maxn;

    for (j=max1;j>=1;j--)

    if (a[j]&&(j+i1=0;j--)

    if (a[j])

    {

    cout

  • 0
    @ 2009-11-14 11:55:43

    MS是最短的一个C++

    #include

    using namespace std;

    int main(){

    int m,n,tv,v,i,j,a[20001]={0};

    a[0]=1;

    cin >> v;

    cin >> n;

    for(i=0;i> tv;

    for(j=v;j>=tv;j--){

    if(a[j]==0){

    a[j] = a[j-tv];

    }

    }

    }

    m = v;

    while(a[m]==0) m--;

    cout

  • 0
    @ 2009-11-11 20:18:00

    so easy

  • 0
    @ 2009-11-11 16:56:11

    Flag    Accepted

    题号   P1133

    类型(?)   动态规划

    通过   5895人

    提交   14178次

    通过率   42%

    难度   2

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    01背包

    超短

    秒杀

    MAIN:

    for i:=1to maxn do

    for j:=maxw downto weight[i]do

    if tot[j-weight[i]]+weight[i]>tot[j]

    then tot[j]:=tot[j-weight[i]]+weight[i];

  • 0
    @ 2009-11-10 18:34:23

    无语了……

    var

    m,n,i,j:longint;

    v,f:array[0..20000] of longint;

    begin

    readln(m);

    readln(n);

    for i:=1 to n do readln(v[i]);

    fillchar(f,sizeof(f),0);

    f[0]:=1;

    for i:=1 to n do

    for j:=m downto v[i] do

    f[j]:=f[j]+f[j-v[i]];

    for i:= m downto 1 do

    if f[i]>0 then

    begin

    writeln(m-i);

    halt;

    end;

    writeln(m);

    end.

  • 0
    @ 2009-11-08 09:57:12

    program ws;

    var a:array[1..30] of longint;

    b:array[1..10000] of longint;

    n,m,gd,i,j,o,k,s,min,f:longint;

    begin

    j:=0;

    readln(n,m);

    for i:=1 to m do

    readln(a[i]);

    for f:=0 to m do

    begin

    o:=f; k:=f; gd:=0;

    while om do

    begin

    if k=0 then gd:=gd+0

    else gd:=gd+a[k];

    for i:=k+1 to m do

    begin

    j:=j+1;

    b[j]:=b[j]+gd+a[i];

    end;

    if i=m then

    begin

    o:=o+1;

    k:=o;

    end;

    end;

    end;

    min:=n-b[1];

    min:=abs(min);

    for i:=2 to j do

    if (b[i]

  • 0
    @ 2009-11-08 00:50:52

    #include "stdio.h"

    #include "stdlib.h"

    int main()

    {

    int n, v, i, j, used[20001], w[31], remain;

    scanf("%d%d",&v,&n);

    for(i=1;i=w[i]) && (used[j-w[i]]+w[i]>used[j]))

    used[j]=used[j-w[i]]+w[i];

    remain=(v-used[v]);

    printf("%d",remain);

    return 0;

    }

    为什么我第五个点不对呢? 求教

  • 0
    @ 2009-11-06 09:10:05

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    ___|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|\__|

    直接背包! 十分钟不到就Ac.

    f[i][j] = f[j];

    if( j >= a[i] && f[j-a[i]]+a[i] > f[i][j]){

    f[i][j] = f[j-a[i]]+a[i];

    }

  • 0
    @ 2009-11-03 20:57:52

    楼下的楼下,to是完全BAG,downto是01BAG。

    详见《背包九讲》

  • 0
    @ 2009-11-02 18:43:24

    与P1104采药的题解差不多...

  • 0
    @ 2009-11-01 22:45:20

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    H2O

    不过有个疑问

    为什么 to 是20分

    downto 就A了?

    Var

    f:array [0..20000] of Boolean;

    a:array [1..30] of Longint;

    i,j,n,v:Longint;

    Function max(a,b:Longint):Longint;

    Begin

    If a>b Then Exit(a) Else Exit(b);

    End;

    Begin

    Readln(v,n);

    For i:=1 to n Do Read(a[i]);

    f[0]:=true;

    For i:=1 to n Do

    For j:=v downto a[i] Do If f[j-a[i]] Then f[j]:=true;{介个地方}

    For i:=v downto 1 Do If f[i] Then Begin

    Writeln(v-i);

    Halt;

    End;

    End.

  • 0
    @ 2009-10-31 22:29:10

    //P1133 装箱问题

    #include

    using namespace std;

    int a[20001];

    int main(){

    int n,v,i,j,x;

    cin>>v>>n;

    a[0]=1;

    for (i=1;i>x;

    for (j=v-x;j>=0;j--){

    if (a[j]){

    a[j+x]=1;

    }

    }

    }

    for (i=v;i>=1;i--){

    if (a[i])break;

    }

    cout

  • 0
    @ 2009-10-26 10:55:32

    水题一道。

    晾一下程序,51题AC。

    program cl(input,output);

    var f:array[0..20000]of boolean;

    a:array[1..30]of longint;

    v,n,i,j,ans:longint;

    begin

    readln(v);

    readln(n);

    for i:=1 to n do

    read(a[i]);

    f[0]:=true;

    for i:=1 to n do

    for j:=v downto a[i] do

    if f[j-a[i]]=true then f[j]:=true;

    for i:=v downto 1 do

    begin

    if f[i] then break;

    inc(ans);

    end;

    writeln(ans);

    end.

  • 0
    @ 2009-10-25 20:03:27

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:运行时错误...|错误号: 216

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:80 有效耗时:0ms

    var f,q:array[0..10000] of longint;

    n,m,i,j,k,a,b,c:longint;

    begin

    read(n,m);

    for i:=1 to m do

    readln(f[i]);

    for i:=1 to m do

    for j:=n downto 1 do

    if f[i]q[j] then q[j]:=a;

    end;

    writeln(n-q[n]);

    end.

    那位仁兄帮我看看哪里错了

  • 0
    @ 2009-10-25 15:27:27

    虽然简单,但却是基础,我认为dp方程还是有必要写一下的:

    f[m,j]=min{f[m-v[j],j-1]+v[j],f[m,j-1]}

    然后用一维的方法来实现就行了。

  • 0
    @ 2009-10-21 15:15:51

    var

    v,i,j,m,n:integer;

    a,b:array[1..20000] of integer;

    begin

    readln(v);

    readln(n);

    for i:=1 to n do

    readln(a[i]);

    for i:= 1 to n do

    for j:=v downto 1 do

    if (a[i]b[j])then b[j]:=m;

    end;

    writeln(v-b[v]);

    end.

  • 0
    @ 2009-10-18 09:10:23

    var

    w:array[0..20000]of integer;

    f:array[1..30]of integer;

    v,n,i,j,d:integer;

    begin

    read(v,n);

    for i:=1 to n do read(f[i]);

    for i:=1 to n do

    for j:=v downto 1 do

    if(f[i]w[j])then w[j]:=d;

    end;

    writeln(v-w[v]);

    end.

    典型用DP解背包的问题,大胆的用O(vn)的方法做。

  • 0
    @ 2009-10-17 12:03:42

    标准0-1背包...

信息

ID
1133
难度
4
分类
动态规划 | 背包 点击显示
标签
递交数
10781
已通过
4478
通过率
42%
被复制
24
上传者