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

问小明有多少种买书方案?(每种书可购买多本)

输入格式:

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

输出格式:

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

数据范围:

0≤n≤1000

输入样例1:

20

输出样例1

2

输入样例2:

15

输出样例2:

0

输入样例3:

0

输出样例3:

1

题目分析

完全背包

代码实现

#include <iostream>
using namespace std;
const int N = 1e3 + 10;

int V, dp[N], v[5] = {0, 10, 20, 50, 100};
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V;
    dp[0] = 1;
    for (int i = 1; i <= 4; ++i) {
        for (int j = 0; j <= V; ++j)if (j >= v[i]) dp[j] += dp[j - v[i]];
    }
    cout << dp[V];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status