SPOJ 384 — Any fool can do it (code: FOOL)
庆祝一下,这道题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] := […]