Poj1187 [NOI2001]陨石的秘密 — 动态规划

Note: 本文最初于 2011年03月17日 星期四 17:58 在 hi.baidu.com/lydrainbowcat 发表。

f[d,i,j,k]表示i对{},j对[],k对()组成深度不大于d的SS串的个数。

目标：f[d,l1,l2,l3]-f[d-1,l1,l2,l3]

注意：用“不大于d”可以把时间从O((l1*l2*l3*d)^2)优化到O(d*(l1*l2*l3)^2)，因为少了一层对d的循环。

每次计算f[d,i,j,k]时，分别假设有一对括号{} []或()，在里面放一些东西组成一个整体，剩下其他的东西在组合成一个整体，然后两部分整体前后相接(即各自方案数相乘)就组成了一种答案。至于里面放什么外边剩什么，只需要枚举里面放多少{} [] ()，即循环枚举一边完事。

对于()我们只能在里面放()

对于[]里面可以放[] ()

对于{}里面可以放{} [] ()

到这里会有一个疑问，两部分整体各自的随意组合很好理解，但是为什么只需要把两个整体的方案数相乘，即前后相接，而不用考虑把一部分整体放到另一部分的里边？其实很容易想到，这种情况在枚举最外面一层括号的里边的组合方案时，就已经将其计算在内。

注意d=0的情况，此时若d,l1,l2,l3均为0则输出1(空串也是SS串，细节要注意)，否则输出0。

还有一个需要注意的地方：由于最后输出f[d,l1,l2,l3]-f[d-1,l1,l2,l3]，而又是mod了11380的，所以可能减出来负数，所以要先加个11380再mod！

Source Code

Problem: 1187		User: lydliyudong
Memory: 1016K		Time: 594MS
Language: Pascal		Result: Accepted

• Source Code

var
 f:array[0..30,0..10,0..10,0..10]of longint;
 l1,l2,l3,d,i,j,k,l:longint;

function dp(d,a,b,c:longint):longint;
 var
  i,j,k:longint;
 begin
  dp:=0;
  if (a=0)and(b=0)and(c=0) then exit(1);
  if c<>0 then
   for i:=0 to c-1 do
    dp:=(dp+f[d,a,b,c-i-1]*f[d-1,0,0,i])mod 11380;
  if b<>0 then
   for i:=0 to b-1 do
    for j:=0 to c do
     dp:=(dp+f[d,a,b-i-1,c-j]*f[d-1,0,i,j])mod 11380;
  if a<>0 then
   for i:=0 to a-1 do
    for j:=0 to b do
     for k:=0 to c do
      dp:=(dp+f[d,a-i-1,b-j,c-k]*f[d-1,i,j,k])mod 11380;
 end;

begin
 readln(l1,l2,l3,d);
 f[0,0,0,0]:=1;
 for i:=1 to d do
  for j:=0 to l1 do
   for k:=0 to l2 do
    for l:=0 to l3 do
     f[i,j,k,l]:=dp(i,j,k,l)mod 11380;
 if d<>0 then writeln((f[d,l1,l2,l3]+11380-f[d-1,l1,l2,l3])mod 11380)
 else writeln(f[d,l1,l2,l3]);
end.

šš