AcWing 1023.买书

HYLW · 2024-02-21 16:46:13 · 题解

• 题目描述

小明手里有 n 元钱全部用来买书，书的价格为 10 元， 20 元，50 元， 100 元。

问小明有多少种买书方案？（每种书可购买多本）

• 输入格式

一个整数 n，代表总共钱数。

• 输出格式

一个整数，代表选择方案种数。

• 数据范围

• 输入样例1：

20

• 输出样例1：

2

• 输入样例2：

15

• 输出样例2：

0

• 输入样例3：

0

• 输出样例3：

1

• 解：

不想多说，看代码。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int v[4]={10,20,50,100};
int f[N];//表示凑出 n 元的方案数
//f[i,j]=f[i-1,j]+f[i-1,j-v[i]]+f[i-1,j-2v[i]]+……
//f[i,j-v[i]]=f[i-1,j-v[i]]+f[i-1,j-2v[i]]+……
//f[i,j]=f[i-1,j]+f[i,j-v[i]] 
int n;

int main(){
    scanf("%d",&n);
    f[0]=1;
    for(int i=0;i<4;i++)
        for(int j=v[i];j<=n;j++)
            f[j]+=f[j-v[i]];

    printf("%d",f[n]);
    return 0;
}