NOT A BLOG | sqybi

SPOJ 384 — Any fool can do it (code: FOOL)

Posted on 四月 22nd, 2008.

庆祝一下,这道题AC之后得到了宝贵的0.4分,于是以4.4分的成绩拿到了1000名…整1000名啊…一个不差…
截图就不发了…

这道题是一道挺弱智的DP,和冰峰文有些类似,比那个还要简单.
dset[l, r]表示从l到r这一段是不是一个set,而dlist[l, r]表示l到r是不是list.然后转移的时候考虑全就可以.
其中判断是set,除了特殊情况以外,只要判断l+1到r-1是不是list就行.但注意如果a[l],a[r]不是’{'和’}',一定不是set.
判断是list的复杂些,除了特殊情况(就是atom的情况),还需要判断这一段是不是set(set也是一个list).然后枚举中间的每一位,如果某一位是’,',那么看它两侧的串是不是两个list,是的话就说明l到r也是list.

实现不难,不过写错了一点,把l+1打成了l+r.winsty说的没错,一定要小心啊…刷1Y率是关键…

{
SPOJ 384; Any fool can do it; FOOL
- sqybi’s code
- DP
}
program fool_sqybi;
  const
    nn = 200;

  var
    a: string;
    times, cases, n: longint;
    dset, dlist: array[1..nn, 1..nn]of longint;

  procedure flist(l, r: longint); forward;

  procedure fset(l, r: longint);
    begin
      if l = r then begin
        dset[l, r] := 0;
        exit;
      end;
      if l = r - 1 then begin
        if (a[l] = ‘{’) and (a[r] = ‘}’) then
          dset[l, r] := 1
        else
          dset[l, r] := 0;
        exit;
      end;
      dset[l, r] := 0;
      if (a[l] <> ‘{’) or (a[r] <> ‘}’) then exit;
      if dlist[l+1, r-1] = -1 then flist(l+1, r-1);
      dset[l, r] := dlist[l+1, r-1];
    end;

  procedure flist(l, r: longint);
    var
      i: longint;
    begin
      if l = r then begin
        dlist[l, r] := 1;
        exit;
      end;
      dlist[l, r] := 1;
      if dset[l, r] = -1 then fset(l, r);
      if dset[l, r] = 1 then exit;
      for i:=l+1 to r-1 do
        if a[i] = ‘,’ then begin
          if dlist[l, i-1] = -1 then flist(l, i-1);
          if dlist[i+1, r] = -1 then flist(i+1, r);
          if (dlist[l, i-1] = 1) and (dlist[i+1, r] = 1) then exit;
        end;
      dlist[l, r] := 0;
    end;

  begin
    readln(cases);
    for times:=1 to cases do begin
      readln(a);
      n := length(a);
      fillchar(dset, sizeof(dset), $FF);
      fillchar(dlist, sizeof(dlist), $FF);
      fset(1, n);
      if dset[1, n] = 1 then
        writeln(’Word #’, times, ‘: Set’)
      else
        writeln(’Word #’, times, ‘: No Set’)
    end;
  end.

阅读(143 次)

Make a Comment

Make A Comment: ( 2 so far )

2 Responses to “SPOJ 384 — Any fool can do it (code: FOOL)”

Comments RSS Feed

Where's The Comment Form?