首页 > [恩难到了]陨石的秘密

[恩难到了]陨石的秘密

【描述】

公元19881231年,一颗巨大的陨石坠落在世界的政治文化中心cs。于是,灾难降临了,地球上出现了一系列反常的现象。当人们焦急万分的时候,一支由cs科学家组成的考察队赶到了出事地点。经过一番侦察,科学家们发现陨石上刻有若干行密文,每一行都包含5个整数:

 1 1 1 1 6

 0 0 6 3 57

 8 0 11 3 2845

著名的科学家yh发现,这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算,他定义了一种yh表达式

1. yh表达式是仅由'{','}','[',']','(',')'组成的字符串。

2. 一个空串是yh表达式。

3. 如果A是yh表达式,且A中不含字符'{','}','[',']',则(A)是yh表达式。

4. 如果A是yh表达式,且A中不含字符'{','}',则[A]是yh表达式。

5. 如果A是yh表达式,则{A}是yh表达式。

6. 如果A和B都是yh表达式,则AB也是yh表达式。

例如  ()(())[] , {()[()]}, { {[[(())]]}} 都是yh表达式。

而 ()([])() , [() 都不是SS表达式。

并且,我们定义,该串总的括号最大层数为该串的深度,例如(){()}[]的深度为2。

密文中的复杂运算是这样进行的:

设密文中每行前4个数依次为L1,L2,L3,D,求出所有深度为D,含有L1对{},L2对[],L3对()的SS串的个数,并用这个数对数11380求余数,这个余数就是密文中每行的第5个数,我们称之为神秘数。

密文中某些行的第五个数已经模糊不清,而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。

【输入格式】

共一行,4个整数L1,L2,L3,D。相邻两个数之间用一个空格分隔。

【输出格式】

共一行,包含一个整数,即神秘数

【样例输入】

1 1 1 2

【样例输出】

8

【数据范围】

L1,L2,L3<=10,D<=30。

【分析】

恩,很明白,不会……

然后搜题解,找到了BYD大牛。

于是看了题解,于是会了。囧。

以下引用BYD大牛的题解:

“容易看出是动态规划,但是状态转移方程容易考虑不周全。

题目中样例的8种方案为

{[]()} {()[]} {}[()] [()]{} []{()} {()}[] (){[]} {[]}()

可以看出每个SS表达式都可以看成由几个小的SS组成,组成方式可能是嵌套或者连接。如果是嵌套(包括仅1层),我们把这个嵌套体看作一个整体部分,称为一个组。则每个SS表达式都是由几个组连接而成了。

设定 F[p1,p2,p3,d]为深度不超过d,包含p1个{},p2个[],p3个()的SS表达式的可能组成的方案数。S[p1,p2,p3,d]为深度不超过d,包含p1个{},p2个[],p3个()的一个组的可能组成的方案数。

则状态转移方程为

S[p1,p2,p3,d]={0 (p1==p2==p3==0)F[p1-1,p2,p3,d-1] (p1>=1)F[p1,p2-1,p3,d-1] (p1==0 && p2>=1)F[p1,p2,p3-1,d-1] (p1==0 && p2==0 && p3>=1)}

F[p1,p2,p3,d]=Σ(S[x1,x2,x3,d]*F[p1-x1,p2-x2,p3-x3,d]) (0<=x1<=p1,0<=x2<=p2,0<=x3<=p3且x1,x2,x3不同时为0)

初始条件

  • F[0,0,0,i]=1 (0<=i<=D)

最终的结果就是

  • F[L1,L2,L3,D]-F[L1,L2,L3,D-1]”
引用完毕。
#include 
#define maxn 35int f[maxn][maxn][maxn][maxn];
int l1,l2,l3,d,ans,base=11380;
int dp(int p1,int p2,int p3,int d);int s(int p1,int p2,int p3,int d)
{if (p1) return dp(p1-1,p2,p3,d-1);if (p2) return dp(p1,p2-1,p3,d-1);return dp(p1,p2,p3-1,d-1);
}int dp(int p1,int p2,int p3,int d)
{if (d<0) return 0;if (f[p1][p2][p3][d]==-1){f[p1][p2][p3][d]=0;for (int x1=0;x1<=p1;++x1)for (int x2=0;x2<=p2;++x2)for (int x3=0;x3<=p3;++x3){if (x1+x2+x3==0) continue;f[p1][p2][p3][d]+=(s(x1,x2,x3,d)*dp(p1-x1,p2-x2,p3-x3,d))%base;f[p1][p2][p3][d]%=base;}}return f[p1][p2][p3][d];
}int main()
{freopen("secret.in","r",stdin);freopen("secret.out","w",stdout);scanf("%d%d%d%d",&l1,&l2,&l3,&d);for (int i=0;i<=d;++i){for (int p1=0;p1<=l1;++p1)for (int p2=0;p2<=l2;++p2)for (int p3=0;p3<=l3;++p3)f[p1][p2][p3][i]=-1;f[0][0][0][i]=1;}ans=dp(l1,l2,l3,d)-dp(l1,l2,l3,d-1);ans=(ans+base)%base;printf("%d
",ans);return 0;
}

 

 

 

转载于:https://www.cnblogs.com/sephirothlee/archive/2010/09/25/1834775.html

更多相关:

  • 代码: % x = [-0.9, 0.81]; [y, L, B] = QCoeff(x, 3) % Unquantized parameters r = 0.9; theta = pi/3; a1 = -2*r*cos(theta); a2 = r*r; p1 = r*exp(j*theta); p2 = p1';% Quan...

  • 点击打开链接   //求SUM(gcd(i,n), 1<=i<=n) /*g(n)=gcd(i,n),根据积性定义g(mn)=g(m)*g(n)(gcd(m,n)==1)所以gcd(i,n)是积性的,所以f(n)=sum(gcd(i,n))是积性的,f(n)=f(p1^a1*p2^a2*...*pn^an)=f(p1^a1)*f(p...

  • 1 ==    (1)当对象是基本数据类型时,比较值;   (2)当对象是引用型时,比较的是地址值!!1 2 equals():只处理引用型数据;Object类中的equals方法依然比较的是地址值!   但在String,File,Date类重写了equals方法,比较的是值; 3 String类内存解析   Person p1=n...