CF 543A Writing Code 完全背包问题

CF 543A Writing Code 完全背包问题

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly ai bugs in every line of code that he writes.

Let’s call a sequence of non-negative integers v1, v2, …, vn a plan, if v1 + v2 + … + vn = m. The programmers follow the plan like that: in the beginning the first programmer writes the first v1 lines of the given task, then the second programmer writes v2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let’s call a plan good, if all the written lines of the task contain at most b bugs in total.

Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod.

Input

The first line contains four integers nmbmod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 109 + 7) — the number of programmers, the number of lines of code in the task, the maximum total number of bugs respectively and the modulo you should use when printing the answer.

The next line contains n space-separated integers a1, a2, …, an (0 ≤ ai ≤ 500) — the number of bugs per line for each programmer.

Output

Print a single integer — the answer to the problem modulo mod.

Sample test(s)
input

output

input

output

input

output

 

题目如上,根据上文动态规划建模的思路 ,来考虑这个问题,先把上文的建模思路放在下面:

先构造问题对应的过程 ,每个过程都是选出一个人,这个人有两种让这个人写一定行数的代码然后保证bug数小于最多允许的bug数,或者不让这个人写代码.

然后考虑这个问题的最后一步,对于最后一个程序员 ,我们有两种选择,一种是不让他写代码,另一种是让他写r行代码,因而这个问题的状态转移方程可以写为下式:

设dp[i][j][k] 表示前i个程序员写j行代码产生恰好k个错误的情况数

则 dp[i][j][k] = dp[i-1][j][k]+dp[i-1][j-r][k-r*a[i]]  (r>0) 可以看出这是一个完全背包问题,根据背包九讲里的优化方式,完全背包问题可以优化时间复杂度.

采用将01背包的循环改为正序的方法即可以适用与完全背包问题.

另外此题如果开500*500*500的longlong数组的话会MLE 需要滚动数组

AC代码如下

发表评论

电子邮件地址不会被公开。 必填项已用*标注

15 − 5 =