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
3 3 3 100
1 1 1
output
10
input
3 6 5 1000000007
1 2 3
output
0
input
3 5 6 11
1 2 1
output
0

 

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

1、构造问题所相应的过程。

2、思考过程的最后一个步骤,看看有哪些选择情况。

3、找到最后一步的子问题,确保符合“子问题重叠”,把子问题中不同样的地方设置为參数。

4、使得子问题符合“最优子结构”。

5、找到边界,考虑边界的各种处理方式。

6、确保满足“子问题独立”,一般而言,假设我们是在多个子问题中选择一个作为实施方案,而不会同一时候实施多个方案,那么子问题就是独立的。

7、考虑怎样做备忘录。

8、分析所需时间是否满足要求。

9、写出转移方程式。

先构造问题对应的过程 ,每个过程都是选出一个人,这个人有两种让这个人写一定行数的代码然后保证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代码如下

 /*************************************************************************
    > File Name: C.cpp
    > Author: VOID_133
    > ################### 
    > Mail: ################### 
    > Created Time: Mon May 18 22:32:58 2015
 ************************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cstring>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<cstdlib>
#include<ctime>
#include<set>
using namespace std;
 /*MACRO*/
#define FORi(l,r) for(int i=(l);i<(r);i++)
#define FORj(l,r) for(int j=(l);j<(r);j++)
#define FORk(l,r) for(int k=(l);k<(r);k++)
#define MEMSET0(i) memset((i),0,sizeof((i)))
#define MEMSET1(i) memset((i),-1,sizeof((i)))

const int maxn = 502;
int n,m,b;
long long mod;
int a[maxn];
long long dp[2][maxn][maxn];

int main(void)
{
	while(scanf("%d%d%d%I64d",&n,&m,&b,&mod)!=EOF)
	{
		MEMSET0(dp);
		MEMSET0(a);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",a+i);
		}
		dp[0][0][0]=1L;
		dp[1][0][0]=1L;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				//puts("MARKn");
				for(int k=0;k<=b;k++)
				{
					if(a[i]>k)
					{
						dp[i%2][j][k]=dp[(i-1)%2][j][k]%mod;
					}
					else 
					{
						dp[i%2][j][k]=(dp[(i-1)%2][j][k]+dp[i%2][j-1][k-a[i]])%mod;
					}
				}
			}
		}
		long long ans=0;
		for(int i=0;i<=b;i++)
		{
			ans= ( ans + dp[n%2][m][i] ) % mod;
		}
		ans = ans % mod;
		printf("%I64dn",ans);
	}
	return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *

17 + eight =

This site uses Akismet to reduce spam. Learn how your comment data is processed.