Zhiwei Zhang included in Algorithm

2020-10-07 2020-10-07 135 words One minute

Contents

Description

HDU 2566 假设一堆由1分、2分、5分组成的n个硬币总面值为m分，求一共有多少种可能的组合方式（某种面值的硬币可以数量可以为0）。

Solution

坑题，没给数据范围，只能瞎猜，一发搜索挂掉发现无法去重，但是考虑到该问题满足从1开始分配并无后效性，可以直接递推（类似背包），三种物品可选任意次

Code

 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


#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main() {
	//freopen("test.txt", "r", stdin);
	ios::sync_with_stdio(false);
	int N, M;
        int ans;		
        int dp[2000][2000];
        int n[] = {1,2,5};
        cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		cin >> N >> M;
		mem(dp,0);
		dp[0][0] = 1;
		for (int i = 0; i < 3; ++i) {
			for (int j = 1; j <= N; ++j) {
				for (int k = n[i]; k <= M; ++k) {
					dp[j][k] += dp[j-1][k-n[i]];
				}
			}
		}
		cout << dp[N][M] << endl;
	} 
	return 0;
}