加载中…波动数列 （蓝桥杯编程题）（超级好的一个 DP 类型的题）
(2016-02-19 16:34:02)
标签：
it蓝桥杯dp好题 |
分类： ACM |
描述：
想知道长度为 n 和为 s
而且后一项总是比前一项增加a或者减少b的整数数列可能有多少种呢？
输入的第一行包含四个整数 n s a
b，含义如前面说述。
输出一行，包含一个整数，表示满足条件的方案数。由于这个数很大，请输出方案数除以100000007的余数。
观察这个数列： 1 3 0 2 -1 1 -2 ...
这个数列中后一项总是比前一项增加2或者减少3。
【数据格式】
例如，输入：
4 10 2 3
程序应该输出：
2
【样例说明】
这两个数列分别是2 4 1 3和7 4 1 -2。
【数据规模与约定】
对于10%的数据，1<=n<=5，0<=s<=5，1<=a,b<=5；
对于30%的数据，1<=n<=30，0<=s<=30，1<=a,b<=30；
对于50%的数据，1<=n<=50，0<=s<=50，1<=a,b<=50；
对于70%的数据，1<=n<=100，0<=s<=500，1<=a,
b<=50；
对于100%的数据，1<=n<=1000，-1,000,000,000<=s<=1,000,000,000，1<=a,
b<=1,000,000。
分析：
设对于任意一个合法的起始数字 x，（根据题意，只要 x
为整数即可），那么在前一个“基数”的基础上，走下一步时，无非俩种选择，要么 +a，要么
-b，由基数的俩种可能变化，有导出了新的基数，然后对于每一个新的基数，同样俩种可能的变化选择……显然，会出现一个树形的解空间结构。或者，对于每一个状态节点的+/-俩种选择，像极了背包问题对于每个物品的
0-1 取舍，很直接的就可以想到搜索去求解。但是根据数据规模，搜索的时间复杂度为 2^n
， 对于 n<50 的规模还算可以，但题目的数据提示，有一半的数据 n 值都是超过 50
的，显然搜索是不行的……
看了解题报告，原来是 DP，但这个题 DP 的很巧妙，理解之后觉得，它其实是从另一个角度去看问题，没有直接从各个元素值
&& 和的角度入手。
不妨设起始数字为 x ，并且+a/-b 的变化统一标记为 p。那么显然，对于 n
项的和，应该为 x+（x+p）+（x+2p）+……+（x+（n-1）p）
= s。进一步化简有 ： nx+（（n-1）n/2）p = s。显然，对于任意未知的定值 x，操作 a&&b
的次数和是一定的，次数和为 i 倍的 a 或者 i
倍的-b，其变化倍数刚好是权值序列第 i 个数的值。若最终结果中一共有 m 倍的 a，那么 b
的变换倍数显然也就确定了。但是……很明显，对于同一个 a 的总变化倍数 m，合法序列不见得只是 1
种 。显然，结果的次数不知取决于总的变化次数，还取决于变化序列-------->
DP 也就是站在序列的角度上 DP 的，对于权值序列 1 ， 2 ， 3 ……（n-1）进行
DP 。
设函数 dp（i，j）表示序列的前 i 项中 a 的次数为 j
时的方案种数。（这个定义为 前 i 项 a 的次数和为
j，显然，与序列顺序是有关的，即 dp 记录的方案数时与序列有关的，定位到了序列--->显然，只要确定了序列中 a
的各项的选择的分布顺序， b 也就确定了，即为一种合法的变化序列）。
根据 dp 函数的定义，显然有边界条件： dp（i，0） = 1 （i ！= 0）（前
i 项 a 的次数和为 0 ， 即 all b项，只有 1 种可能）； dp（0，j）= 0 （j ！= 0）（前 0 项 a
的次数和非 0 ， 显然是不可能的）
一般的， 若 i > j , 即该项 a 的次数权值 i > 和次数 j，显然该项是不包含在统计中的，so
dp（i，j） = dp（i-1，j）；若 i <= j , 显然该项可以包含在和项 j
中也可以不包含在其中，so dp（i，j） = dp（i-1，j）+dp（i-1，j-i）。
----> DP
实际上是对有序序列进行的。有序序列的合法方案种数。
具体实现时，由上分析，需要记录表 red（x，y），x 即前 i 项，范围 [ 0 , n-1 ] , y 即次数和，范围为
[ 0 , (n-1)*n/2 ] . 需要注意的是，列项的和并不是对若干项元素值的进行计和，而是次数权值序列中 a 的次数进行计和。根据 n
值上限，次数计和最大值不超过 1e6，反之对若干项元素值计和，1e9的数量级，根本就开不下这么大的数组。
同时，n 值虽为 1e3的数量级，但整体空间也是很大的。根据状态转移方程，（i，x）下的状态仅取决于
（i-1，x）下的状态，这个状态转移方程像极了 0-1 背包的 DP 方程，是完全可以状态压缩的，用滚动数组法进行状态压缩。
同时，最终把表 red 求解完后，关于最终结果的得出：
有方程式 ：nx+（（n-1）n/2）p
= s，可以得出
同时，类型小总结，很多看似很像搜索的题甚至搜索就可以解决，只是因为数据规模太大，时间上吼不住时，其实大都是可以 DP
求解的。
有序序列数目的计数问题 --->
DP.
示例代码：
const int Max = 100000007;
const int MaxSum = 1e6;
int n , s , a , b;
int number[2][MaxSum];
int dp(int maxTimes){
int i , j;
// initial the boundry
for(j = 1 ; j <= maxTimes ; ++j){
number[0][j] = 0;
}
number[0][0] = 1;
int cur = 1;
for(i = 1 ; i < n ; ++i){
number[cur][0] = 1;
for(j = 1 ; j < i ; ++j){
number[cur][j] = number[1-cur][j];
}
for(j = i ; j <= maxTimes ; ++j){
number[cur][j] = number[1-cur][j]+number[1-cur][j-i];
}
cur = 1-cur;
}
cur = 1-cur;
for(j = 0 , i = 0 ; j <= maxTimes ; ++j){
if((s-j*a-maxTimes*b+j*b)%n == 0){
i += number[cur][j];
i %= Max;
}
}
return i;
}
int main(int argc, char** argv)
{
scanf("%d%d%d%d" , &n , &s , &a , &b);
int maxTimes = (n-1)*n/2;
cout << dp(maxTimes) << endl;
return 0;
}
喜欢
0
赠金笔
后一篇：蓝桥杯签到题