校赛题目

【原题链接】

【题意说明】

从现有的题目中选择N个从1~N不同难度系数的题目,每个题目分配难度系数,但有些题目的难度不好分配,给这种题目每个分配2个连续的数作为难度系数,在取题时可以任意选择一个难度系数。

问题:给定不同难度系数的若干个题目,输出不同的方案种数C,因为C可能很大,因此只要输出C关于1000000007的余数。

【问题分析】

很显然,若是每个题目只有一个难度系数,此题就变得简单了!问题是有些题目的难度系数有两种!

例如:

N=4
  a[4]={3,3,3,3}
  b[3]={3,2,1}

首先令c[i]为不包括b[i-1]难度的方案总数,d[i]为包括b[i]难度的方案总数;

现在,我们从后往前看,对于最后一个难度c[4]=a[4];d[4]=a[4]+b[3];

然后再看倒数两个难度的,c[3]=c[4]*(a[3]+b[3])+a[3]*d[4]+b[3]*(b[3]-1])/2;

d[3]=c[3]+d[4]*b[2]; 

再看倒数三个难度的,c[2]=c[3]*(a[2]+b[2])+a[2]*d[3]+b[2]*(b[2]-1)/2;

d[2]=c[2]+d[3]*b[1];

最后看全部难度的,c[1]=c[2]*(a[1]+b[1])+a[1]*d[2]+b[1]*(b[1]-1)/2;

d[2]=c[1]+d[2]*b[0]; (注:b[0]=0)

由此可以看出,要计算出当前的d[i],只需要记录上一层的c[i+1]与d[i+1]即可。

这样我们就可以利用三个变量来计算即可!

 

原文地址:https://www.cnblogs.com/ahmasoi/p/2782723.html