当前位置:首页 >> 学科竞赛 >>

COCI 2007 zapis记录


COCI 2007 zapis 记录 问题描述
一个合法的括号序列是一个由左括号、右括号组成的的串,并且它们满足以下的条件: 1. 空串也是合法的。 2. 如果 A 是一个合法的括号序列,那么(A),[A],{A}也是合法的。 3. 如果 A 和 B 都是合法的括号序列,那么 AB 同样合法。 例如,序列[({})]、[](){}、[{}]()[{}]是合法的,而[({

{([、[]({)}、[{}])([{}]非法。 Ivica 找到了一个 MS 合法的序列,但是序列中的某些符号看不清楚了。 编写一个程序计算:用任意括号代替这些模糊的符号使之成为一个合法的序列,一共有多少种方法。由于此 数目可能会非常大,所以你只需要输出它的后 5 位。

输入格式
第 1 行包含 1 个整数 n(2 ? n ? 1,200)表示序列长度。 第 2 行为这个序列,看不清的符号用'?'表示。

输出格式
输出 1 个整数,表示符合条件的方法数。

输入输出样例
Zapis1.in 6 ()()() Zapis1.out 1 Zapis2.in 10 (?([?)]?}? Zapis2.out 3 Zapis3.in 16 ???[???????]???? Zapis3.out 92202

提示:第 2 个测试数据中,3 种方法分别是({([()])})、()([()]{})、([([])]{})。

- 1 -

2012-08-23

COCI 2007 zapis 记录 算法分析:dp 记忆化搜索
读入字符串 s 对于从 i 到 j 的串 s[i..j],若有 i+1 ? k ? r, 且 s[i]和 s[k]组成括号(如‘()’,'[]','{}',或 s[i] s[k]有一个是'?') 则 s[i] s[k]将 s[i..j]分为 s[i+1..k-1]与 s[k+1..r]两部分 则加入串 s[i+1..k-1]可分的种数与串 s[k+1..r]可分种数的积(分类计数原理) 即 inc(f[i,j],f[i+1,k-1] ? f[k+1])} const maxn=201; a:string='([{';b:string=')]}'; var f:array[0..maxn,0..maxn]of int64; v:array[0..maxn,0..maxn]of boolean; n,i,j:longint; ans:int64; s:string; function dp(left,right:longint):int64; var i,j:longint; begin if left>right then exit(1); if v[left,right] then exit(f[left,right]); f[left,right]:=0; for i:=left+1 to right do for j:=1 to 3 do if (s[left]=a[j])or(s[left]='?') then if (s[i]=b[j])or(s[i]='?') then begin f[left,right]:=f[left,right]+dp(left+1,i-1)*dp(i+1,right); if f[left,right]>100000 then f[left,right]:=f[left,right] mod 100000+100000;
{判断输出是否补 0?如果 mod 以后,如果 ans>100000 则补 0}

end; v[left,right]:=true; exit(f[left,right]) end; begin assign(input,'zapis.in'); reset(input); assign(output,'zapis.out'); rewrite(output); fillchar(v,sizeof(v),0); readln(n);readln(s); ans:=dp(1,n); if ans<100000 then writeln(ans) else begin ans:=ans mod 100000; if ans<10 then write('0000') else if ans<100 then write('000') else if ans<1000 then write('00') else if ans<10000 then write('0'); writeln(ans) end; close(input); close(output); end.

- 2 -

2012-08-23


相关文章:
COCI 2007 zapis记录
- 1 - 2012-08-23 COCI 2007 zapis 记录 算法分析:dp 记忆化搜索读入字符串 s 对于从 i 到 j 的串 s[i..j],若有 i+1 ? k ? r, 且 s[i]和...
更多相关标签:
coci sa | coci 2015 | 天枰coci | excel2007记录单 | 2007到2015藏宝图记录 | word2007找回历史记录 | word2007历史记录 | 2007年开奖记录完整版 |