uva 674 Coin Change 完全背包求装满背包的方案数

缘起

继续浪费生命~ uva 674 Coin Change

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
用1、5、10、25、50 这五个数去凑给定的数n，问有多少种方案。

【输入】
每行一个n(n<=7489)

【输出】
方法数

【样例输入】
11
26

【样例输出】
4
13

【限制】
3s

有了【1】，这就是水题~ 切之~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

int a[7], n, dp[8000];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	a[1] = 1, a[2] = 5, a[3] = 10, a[4] = 25, a[5] = 50;
	while(~scanf("%d", &n))
	{
		memset(dp,0,sizeof(dp));
		dp[0] = 1;
		for (int i = 1;i<=5; i++)
		{
			for (int v = a[i];v<=n; v++)
			{
				dp[v] += dp[v-a[i]];
			}
		}
		printf("%d\n", dp[n]);
	}
	return 0;
}

ac情况

Status Accepted
Time 1120ms
Length 476
Lang C++11 5.3.0
Submitted 2019-10-27 13:40:42
Shared
RemoteRunId 24110452

参考

【1】https://yfsyfs.github.io/2019/10/27/hdu-1284-%E9%92%B1%E5%B8%81%E5%85%91%E6%8D%A2%E9%97%AE%E9%A2%98-%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E6%B1%82%E6%8C%87%E5%AE%9A%E5%AE%B9%E9%87%8F%E6%96%B9%E6%A1%88%E6%95%B0/