题解

55 条题解

  • 0
    @ 2009-08-13 20:12:22

    第一行要特殊处理~~~~~~~~

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

  • 0
    @ 2009-07-28 10:44:44

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案错误...

     ├ 标准行输出

     ├ 错误行输出

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

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

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

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

    哪位大牛帮忙解释一下阿!!!

  • 0
    @ 2009-07-13 23:11:39

    位运算的好题!

  • 0
    @ 2009-06-07 11:11:46

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    这题真不错,我喜欢。

  • 0
    @ 2009-04-13 22:42:37

    编译通过...

  • 0
    @ 2009-04-04 10:47:09

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

  • 0
    @ 2009-03-24 17:26:47

    编译通过...

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

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

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

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

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

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

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

    ├ 测试数据 08:答案错误... ├ 标准行输出

     ├ 错误行输出

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

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

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

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

    怎么回事

  • 0
    @ 2009-03-03 18:38:01

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    const maxn=101; max=201;

    //====================================================

    var n,m,sum:longint;

    b,tot:array[0..max] of longint;

    f:array[0..maxn,0..max,0..max] of longint;

    map:array[0..maxn] of longint;

    //====================================================

    procedure init;

    var i,j:longint;

    ch:char;

    begin

    readln(n,m);

    for i:=1 to n do

    begin

    map[i]:=0;

    for j:=1 to m do

    begin

    read(ch);

    if ch='H' then map[i]:=map[i]+1 shl (j-1);

    end;

    readln;

    end;

    end;

    //====================================================

    procedure predo;

    var i,j,t:longint;

    flag:boolean;

    begin

    sum:=0;

    for i:=0 to 1 shl m-1 do

    begin

    flag:=true; t:=0;

    for j:=1 to m do

    if (i shr (j-1)) mod 2=1 then

    begin

    if ((i shr (j)) mod 2=1)or((i shr (j+1)) mod 2=1) then flag:=false;

    inc(t);

    end;

    if flag then

    begin inc(sum); b[sum]:=i; tot[sum]:=t; end;

    end;

    end;

    //====================================================

    procedure main;

    var i,j,k1,k2,ans:longint;

    begin

    ans:=0;

    for i:=1 to n do

    for j:=1 to sum do

    begin

    if (map[i])and(b[j])0 then continue;

    if i=1 then f:=tot[j];

    if i=2 then

    begin

    for k1:=1 to sum do

    begin

    if (map)and(b[k1])0 then continue;

    if (b[j])and(b[k1])0 then continue;

    if f+tot[j]>f then f:=f+tot[j];

    end;

    end else

    for k1:=1 to sum do

    begin

    if (map)and(b[k1])0 then continue;

    if (b[j])and(b[k1])0 then continue;

    for k2:=1 to sum do

    begin

    if (map)and(b[k2])0 then continue;

    if (b[j])and(b[k2])0 then continue;

    if (b[k1])and(b[k2])0 then continue;

    if f+tot[j]>f then f:=f+tot[j];

    end;

    end;

    end;

    for i:=1 to n do

    for j:=1 to sum do

    for k1:=1 to sum do

    if f>ans then ans:=f;

    writeln(ans);

    end;

    //====================================================

    begin

    init;

    predo;

    main;

    end.

    • @ 2014-07-05 18:04:27

      编译不过我会瞎说?

  • 0
    @ 2009-02-27 20:08:26

    核心代码

    function can(x:longint):boolean;

    var p,i:longint;

    begin

    p:=3;

    for i:=1 to m-1 do

    begin

    if p and x=p then exit(false);

    p:=p*2;

    end;

    p:=5;

    for i:=1 to m-2 do

    begin

    if p and x=p then exit(false);

    p:=p*2;

    end;

    exit(true);

    end;

    function can1(x,s:longint):boolean;

    begin

    exit(s or a[x]=a[x]);

    end;

    function can2(x,y:longint):boolean;

    var p:longint;

    begin

    if g[x,y]0 then exit(g[x,y]=1);

    p:=1 shl m-1-b[x,1];

    if b[y,1]or p=p then g[x,y]:=1

    else g[x,y]:=-1;

    exit(g[x,y]=1);

    end;

    function num(x:longint):longint;

    var i:longint;

    begin

    num:=0;

    for i:=0 to m-1 do

    if(x and(1 shl i)=1 shl i)then inc(num);

    end;

    procedure makeb;

    var i:longint;

    begin

    t:=0;

    for i:=0 to(1 shl m-1)do

    if can(i)then

    begin

    inc(t);

    b[t,1]:=i;

    b[t,2]:=num(i);

    end;

    end;

    procedure do1;

    var i:longint;

    begin

    for i:=1 to t do

    if can1(1,b)then f[1,1,i]:=b;

    end;

    procedure do2;

    var i,j:longint;

    begin

    for i:=1 to t do

    if can1(1,b)then

    begin

    for j:=1 to t do

    if can1(2,b[j,1])then

    begin

    if not(can2(i,j))then continue;

    f[2,i,j]:=f[1,1,i]+b[j,2];

    end;

    end;

    end;

    procedure don;

    var i,j,k,l,o:longint;

    begin

    for i:=3 to n do

    begin

    for j:=1 to t do

    if can1(i-1,b[j,1])then

    begin

    for k:=1 to t do

    if can1(i,b[k,1])then

    begin

    f:=0;

    for l:=1 to t do

    if can1(i-2,b[l,1])then

    begin

    if not(can2(j,k))then continue;

    if not(can2(k,l))then continue;

    if not(can2(j,l))then continue;

    o:=f+b[k,2];

    if f

  • 0
    @ 2009-02-07 16:22:05

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    我喜欢这题啊!!!!!

  • 0
    @ 2009-01-27 16:49:17

    爽!!

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-01-21 14:46:47

    有没有哪位大牛发程序来看一下啊?

  • 0
    @ 2009-01-05 18:09:51

    背景 Background

    北京奥运会开幕了,这是中国人的骄傲和自豪,中国健儿在运动场上已经创造了一个又一个辉煌,super pig也不例外………………

    这是什么..

  • 0
    @ 2008-12-15 11:01:04

    位运算

  • 0
    @ 2008-12-13 23:47:14

    刘亦菲给我口交。

  • 0
    @ 2008-12-02 16:37:25

    话说这题福建一位大牛是用来当深搜剪枝的例题用的,DP压位是标准做法毋庸置疑,多讲也没意思.

    Orz深搜全过的大牛若干

  • 0
    @ 2008-11-29 22:34:24

    注意到题目列数只有10,而且炮兵在同一行中还不能互相攻击,因此一行的所有排列方式非常少,可以用二进制表示状态,经过搜索(见程序),10列下的状态也只有60种。

    因为一个炮兵可以影响上下两个,所以状态中还必须考虑到i-1行的状态。

    先讲一下二进制的状态表示法,约定如果列i有兵,则第i位为1,其他没有兵的列都是0。这样我们判断冲突的时候会非常方便:

    状态i和j不冲突(没有兵在同一列)的表示就是 I and j=0

    状态i包含于状态j(在判断状态i是否适用于某行的地形用到) I or j=i

    F表示前i行,第i行状态j,第i-1行状态k的最大炮兵数。

    方程式

    F=max{f}+状态j的兵数

    前提是j,k,l不冲突,且k,l,j分别可以放在各自行的地形。

    最后在最后一行找一下最大就行啦。

    1424.pas

  • 0
    @ 2008-11-11 19:01:54

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    ......写了一个多小时......

  • 0
    @ 2008-11-09 17:36:26

    编译通过...

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-11-08 09:09:59

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    第一次写完总觉得不对,检查了半天发现位运算写错!

信息

ID
1424
难度
5
分类
动态规划 | 状态压缩DP 点击显示
标签
(无)
递交数
1255
已通过
460
通过率
37%
被复制
6
上传者