题解

265 条题解

  • 0
    @ 2012-07-26 00:15:46

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 119ms

    ├ 测试数据 09:答案正确... 244ms

    ├ 测试数据 10:答案正确... 244ms

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

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

    直接裸背包就可以过。stl的set小数据有优势,

    大数据的时候,基本上10000个点每个都访问了。

    所以直接变成10000*lg10000=4倍时间

    然后stl速度大家懂的,就会T了。

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    #include

    using namespace std;

    int n;

    int dp[100][11004];

    int dd[104][104];

    int cnt[10004];

    int sum;

    void solve(){

    int tv;

    int pos;

    sum = 0;

    memset(dp,0,sizeof(dp));

    memset(cnt,0,sizeof(cnt));

    for (int i = 0; i < n; i++)

    {

    dp[i][0] = 1;

    for (int j = 1; j = 0; k--)

    if (dp[i][k])

    dp[i][k + dd[i][j]] = 1;

    }

    for (int j = 0; j

  • 0
    @ 2012-07-21 18:44:19

    这题很坑爹。。直接100个背包就行了**不用担心超复杂度**。。另外注意一定不要用vector记录数据。。不然会超时!最好在线做。。记录所有城堡最小值貌似对时间优化不是很大。。

  • 0
    @ 2010-07-08 08:41:29

    var

    a,b:array[0..10000]of 0..1;

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

    begin

    read(n);

    fillchar(a,sizeof(a),0);

    for i:=1 to n do

    begin

    fillchar(b,sizeof(b),0); b[0]:=1; read(m);

    while m-1 do

    begin

    for j:=10000-m downto 0 do

    if b[j]=1 then b[j+m]:=1;

    read(m);

    end;

    for j:=0 to 10000 do

    if b[j]=0 then a[j]:=0

    else if i=1 then a[j]:=1;

    end;

    k:=0;

    for i:=1 to 10000 do

    if a[i]=1 then k:=i;

    write(k);

    end.

  • 0
    @ 2010-07-06 17:35:35

    本该很简单的背包问题。却 WA 了几次

    var

    b:Array[1..100,0..10000] of boolean;

    n,i,j,max,maxx,x:longint;

    begin

    readln(n);

    for i:=1 to n do

    begin

    read(x); max:=0; b[i][0]:=true;

    while x-1 do

    begin

    for j:=x+max downto x do

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

    max:=x+max; read(x)

    end;

    if max>maxx then maxx:=max

    end;

    for i:=maxx downto 0 do

    begin

    for j:=1 to n do

    if not b[j][i] then break;

    if not b[j][i] then continue;

    break

    end;

    writeln(i)

    end.

  • 0
    @ 2010-04-09 20:59:12

    优化前:

    编译通过...

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

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

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

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

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

    ├ 测试数据 06:答案正确... 72ms

    ├ 测试数据 07:答案正确... 72ms

    ├ 测试数据 08:答案正确... 275ms

    ├ 测试数据 09:运行超时...

    ├ 测试数据 10:答案正确... 884ms

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

    Unaccepted 有效得分:90 有效耗时:1303ms

    优化后:

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 88ms

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

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

    。。。其实就是背包吧。

  • 0
    @ 2010-04-04 14:12:11

    var

    f:array[1..100,0..10000] of integer;

    i,max,k,smax,p,n,x:integer;

    begin

    readln(n);

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

    for i:=1 to n do begin

    max:=0;

    f:=1;

    while true do begin

    read(x);

    if x=-1 then break;

    for k:=max downto 0 do begin

    if f=1 then begin

    f:=1;

    if k+x>max then max:=k+x;

    end;

    end;

    end;

    if smax

  • 0
    @ 2010-03-18 21:16:59

    still,你a数组的第二维要开大,要到10000,才不会201

  • 0
    @ 2010-03-17 16:36:42

    能帮我看看为什么有几组答案错误呢

    var

    a:array[1..100,0..500]of boolean;

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

    x,y,i,k,n,m,max,max1,p:longint;

    begin

    readln(n);

    for x:=1 to n do

    begin

    k:=1;

    repeat

    read(b[k]);

    if b[k]=-1 then readln else

    begin

    max:=max+b[k];

    a[x,b[k]]:=true;

    m:=k;y:=b[k];

    if m1 then

    begin

    for i:=1 to m-1 do

    begin

    inc(k);

    b[k]:=y+b[i];

    a[x,b[k]]:=true;

    end;

    end;

    inc(k);

    if b[k]=-1 then b[k]:=0;

    end;

    until b[k]=-1;

    if max>max1 then max1:=max;

    max:=0;

    end;y:=0;

    for i:=1 to 100 do a:=true;

    while (max1>0)and(p=0) do

    begin

    for i:=1 to n do

    if a=false then y:=1;

    if y=0 then

    begin

    write(max1);

    p:=1;

    end

    else

    dec(max1);y:=0;

    end;

    if max1=0 then write('0');

    end.

  • 0
    @ 2010-03-03 14:14:16

    设F[J]为长度为J的积木的个数,令F[J]=N 解即为 J

    做法:

    1.每一组积木均算出可达到的高度HIGHT(产生高度)

    2.map表示能否达到长度为I的积木(记录)

    同时记录达到高度为I的组数 即 INC(F);(注意判断本组是否有2个达到I高度的解)

    3.计算出最大高度MAXHIGHT

    4.输出自己想-_-

    第一次写题解 请多多包涵0.0

  • 0
    @ 2010-03-02 20:46:10

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 72ms

    ├ 测试数据 10:答案正确... 56ms

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

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

    速度还挺快..

    #include

    #include

    using namespace std;

    int n,k,i,j,ma;

    bool g[10010],f[10010];

    int main()

    {

    /*freopen("p1059.in","r",stdin);

    freopen("p1059.out","w",stdout);*/

    scanf("%d",&n);memset(g,true,sizeof(g));

    for(i=1;ima) ma=j+k;

    }

    }

    for(j=0;j=0;i--)

    if (g[i])

    {

    printf("%d\n",i);

    return 0;

    }

    }

  • 0
    @ 2009-11-11 23:02:24

    弱弱的问一句

    for j:=h downto 0 do

    if (f[j]=1) and (f[j+k]=0) then

    begin

    f[j+k]:=1;inc(g[j+k]);

    end;

    改成

    for j:=k to h do

    if (f[j-k]=1) and (f[j]=0) then

    begin

    f[j]:=1;inc(g[j]);

    end;

    为什么不对?

  • 0
    @ 2009-11-09 12:16:44

    2星纪念

  • 0
    @ 2009-11-07 16:16:55

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 1ms

    ├ 测试数据 10:答案正确... 2ms

  • 0
    @ 2009-11-07 11:16:09

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 88ms

    ├ 测试数据 10:答案正确... 88ms

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

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

    悲剧啊!!!!!!!!!

    终于通过了,今天是RP爆发。一定要去买彩票,中几个亿回来。。。。。。。。。

  • 0
    @ 2009-11-04 18:05:41

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案正确... 150ms

    ├ 测试数据 09:答案正确... 541ms

    ├ 测试数据 10:答案正确... 556ms

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

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

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

    不是很好看,不过经过优化后的双层dp居然一次Ac了.

    题解:

    嵌套动态规划,外层动态规划解决这样的问题,前i层保持高度j是否能做到,即0或1。则f[i][j] = f[j] 且j能够由第i座塔的积木构成。判断积木构成依靠内层动态规划。g[x][i][j]表示前i块积木是否能构成长度j,x表示第x座塔。g[x][i][j] = min{ g[x][j], g[x][i][j-a[x][i]]}; 由于空间需求比较大,考虑使用滚动数组,并将内存动态规划作为预处理进行。

  • 0
    @ 2009-11-04 11:17:49

    哎,有点失落,没秒杀

  • 0
    @ 2009-11-04 10:39:48

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:运行超时|无输出...

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 25ms

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

    Unaccepted 有效得分:90 有效耗时:34ms

    program jimu;

    var i,j,k,n,x,high,max:longint;

    f:array[0..15000]of boolean;

    a:array[1..15000]of integer;

    begin

    readln(n);

    f[0]:=true;

    for k:=1 to n do

    begin

    read(x);

    high:=0;

    while (x-1) do

    begin

    inc(high,x);

    for i:=high downto 0 do

    if not(f) and (f[i]) then

    begin

    f[x+i]:=true;

    inc(a[x+i]);

    end;

    read(x);

    end;

    if max

  • 0
    @ 2009-11-01 09:16:04

    就是判定性的背包问题

  • 0
    @ 2009-10-31 17:27:47

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:答案正确... 9ms

    ├ 测试数据 10:答案正确... 56ms

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

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

    郁闷 没秒杀。本菜惭愧in

  • 0
    @ 2009-10-29 22:01:04

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

    var

    n,min,m,i,j,k,x,con:integer;

    count:array[1..100]of integer;

    h:array[1..100,1..100]of integer;

    f:array[1..100,0..100,0..6000]of boolean;

    kai,kk:boolean;

    begin

    readln(n);

    min:=maxint;

    for i:=1 to n do

    begin

    read(x);

    con:=0;

    m:=0;

    while x-1 do

    begin

    inc(con);

    h:=x;

    f:=true;

    m:=m+x;

    read(x);

    end;

    if m

信息

ID
1059
难度
6
分类
动态规划 | 背包 点击显示
标签
(无)
递交数
7828
已通过
2342
通过率
30%
被复制
19
上传者