hdu 1398 Square Coins 完全背包指定容量方案数

缘起

【1】中研究了 “完全背包问题和01背包问题中恰好装满的方法数” 这一问题. 本文继续学习~ hdu 1398 Square Coins

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
有17种货币，面额分别为i*i(1<=i<=17),都为无限张，给定一个值n（1<=n<=300）,求用上述货币能使价值总和为n的
方案数

【输入】
每行一个n

【输出】
对每个样例输出方法数

【样例输入】
2
10
30
0

【样例输出】
1
4
27

【限制】
1s

【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
30
31
32
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

int a[20], n, dp[305];

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	for (int i = 1;i<=17;i++)
	{
		a[i] = i*i;
	}
	while(scanf("%d", &n), n)
	{
		memset(dp,0,sizeof(dp));
		dp[0] = 1;
		for (int i = 1;i<=17; 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
Memory 1736kB
Length 472
Lang C++
Submitted 2019-10-27 13:31:07
Shared
RemoteRunId 31130818

参考

【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/