寒假打卡——AcWing1371. 货币系统

2021-01-23

货币系统

题意
给定 V 种货币(单位:元),每种货币使用的次数不限。

不同种类的货币,面值可能是相同的。

现在,要你用这 V 种货币凑出 N 元钱,请问共有多少种不同的凑法。

思路:
对于题目给出的数据 我们顺次推即可得到下列这样的二维表

0 1 2 3 4 5 6 7 8 9 10

1 1 1 1 1 1 1 1 1 1 1 1

2 1 1 2 2 3 3 4 4 5 5 6

5 1 1 2 2 3 4 5 6 7 8 10

不难发现 f[2][1]=f[1][1]
f[2][2]=f[1][2]+f[1][0]
f[2][3]=f[1][3]+f[1][1]
f[2][4]=f[1][4]+f[2][2]+f[2][0]

用 y 总的 Dp 分析法即定义 f[x][y]表示为前 i 个物品中选出体积恰好为 j 的方案数为多少

状态转移的时候分析:对于第 i 个物品有以下几种选择:

*选 0 个即不选第 i 个物品
*选 1 个
*选 2 个
....

便可推出 f[i][j]=f[i][j]+f[i-1][j-k*w[i]] (k 从 0 到 j-w[i]>=0 枚举即可)

本以为复杂度可能会超但是提交之后就过了很奇怪,,,感觉 O(N^3),应该可以化简吧

一个本地跑可以能会超的数据
25 10000
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5
反正我的程序跑了一会才出结果。

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+10;

typedef  long long LL;

LL f[30][N];
LL w[30];

int main()
{
	int n,v;
	cin>>n>>v;
	for(int i=1;i<=n;i++) {
		cin>>w[i];
	} 
	
	f[0][0]=1;
	
	
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=v;j++) {
			for(int k=0;j-k*w[i]>=0;k++) {
				f[i][j]+=f[i-1][j-k*w[i]];
			}
		}
	}
	
	
	/*
	for(int i=1;i<=n;i++) {
		for(int j=0;j<=v;j++) {
			cout<<f[i][j]<<' ';
		} 
		puts("");
	}
	*/
	cout<<f[n][v]<<'\n';
	
	return 0;
}

标题:寒假打卡——AcWing1371. 货币系统
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/23/1611390996753.html