Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

要是超时了可以看看这篇

Posted by a280920481 at 2018-10-16 23:24:00 on Problem 1742
In Reply To:贴个标准DP代码 内附详细讲解 Posted by:a280920481 at 2018-10-16 23:17:18
> 
> #include <iostream>//使用优递推的动态规划题,此题可以化成单数列的递推,也可以化为 0 1 数列
> using namespace std;//递推关系:如果 dp[i]>=0 (意味着此处已经可以用之前的硬币组成) 那么dp[i]赋值为0,也就是只需要 0 个当前硬币即可组成
> //                     如果 dp[i]==-1 (意味着此处不能用之前的硬币组成) 那么dp[i]就赋值为 dp[i-当前硬币的币值]+1 (但需提前判断dp[i-当前硬币的币值]是否存在并且小于当前硬币的总数)
> //                     被记录为 非负的位置,永远不会再等于 -1(初始值)  最终不是 -1 的位置就是可以达成的价格
> 
> int N = 0, M = 0;//硬币种数 最大价格
> int A[1001], C[1001];//硬币币值 硬币数量
> int dp[100001];//记录在当前硬币情况下,为了组成价格[],使用此硬币的最少数量,如果不可能则为 -1
> int ans;//记录最终输出的结果
> 
> int main()
> {
> 	while (true)
> 	{
> 		scanf("%d%d", &N, &M);
> 		if (!N)
> 		{
> 			return 0;
> 		}
> 		memset(dp, -1, sizeof(dp));//可以将数组赋值为 -1
> 
> 		for (int i = 0; i < N; i++)
> 		{
> 			scanf("%d", &A[i]);
> 		}
> 		for (int i = 0; i < N; i++)
> 		{
> 			scanf("%d", &C[i]);
> 		}
> 
> 		dp[0] = 0;
> 
> 		for (int i = 0; i < N; i++)
> 		{
> 			for (int j = 0; j <= M; j++)
> 			{
> 				if (dp[j] >= 0)
> 				{
> 					dp[j] = 0;
> 				}
> 				else if(j >= A[i])
> 				{
> 					if (dp[j - A[i]] < C[i])
> 					{
> 						if (dp[j - A[i]] >= 0)
> 						{
> 							dp[j] = dp[j - A[i]] + 1;
> 						}
> 					}
> 				}
> 			}
> 		}
> 
> 		ans = 0;
> 		for (int i = 1; i <= M; i++)
> 		{
> 			if (dp[i] >= 0)
> 			{
> 				ans++;
> 			}
> 		}
> 		printf("%d\n", ans);
> 	}
> 	return 0;//记得加 return 0; 否则VS2017虽然能够编译,但是在OJ上会超时
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator