1、商店购物 (shopping.c/cpp/pas)

在滨海市开着 n 家商店,编号依次为 1 到 n,其中编号为 1 到 m 的商店有日消费量上 限,第 i 家商店的日消费量上限为 wi。 海霸王每次购物的过程是这样的:依次经过每家商店,然后购买非负整数价格的商品,并 在结账的时候在账本上写上在这家商店消费了多少钱。当然,他在这家商店也可以什么都不 买,然后在账本上写上一个 “0”。 这一天,海霸王日常完成了一次购物,但是他不慎遗失了他的账本。他只记得自己这一 天一共消费了多少钱,请写一个程序,帮助海霸王计算有多少种可能的账单。

Input 第一行包含三个正整数 n, m, k,分别表示商店的个数、有限制的商店个数以及总消费量。 第二行包含 m 个整数,依次表示 w1, w2, ..., wm。

Output 输出一行一个整数,即可能的账单数,由于答案可能很大,请对 109 + 7 取模输出。

Notes 100% 的数据,1 ≤m ≤ n,0 ≤ wi ≤ 300,1 ≤ n, k ≤ 5000000。

测试点编号 n m wi k

约定

1-2 ≤100 ≤100 ≤100 ≤1000 n=m

3-5 ≤100 ≤100 ≤300 ≤100000 无

6-7 ≤5000000 ≤20 ≤300 ≤5000000 无

8-10 ≤5000000 ≤300 ≤300 ≤5000000 无


solution

我们考虑特殊处理有限制的商店。

令f[i][j]表示前i个商店花j元钱的方案数。

f[i][j]= f[i-1][k]   j-v[i] <= k <= j

可以前缀和优化成n*sumw的

剩下的就是插板法乱选了

05-11 22:07