本文共 969 字，大约阅读时间需要 3 分钟。

题目大意

题面很好理解，

思路分析

由于条件中该机器一次性最多能买k张票，因此将问题进行分解

1. 先算出在票数 <=k的范围内，买i张票所需的最小纸币数，用minv1[]存储，即对应于机器购买一次的情况，可用贪心算出。
2. 当前需要买n张票，用minv2[]存储当前所需的最小纸币数，其中j的取值范围比较关键，我的理解是通过j的取值，与算出的minv1[]进行关联，从而达到多次购票的效果，相应的动态转移方程为

i:1->n	j:1->min(i,k)	动态转移方程:	minv2[i]=min(minv2[i],minv2[i-j]+minv1[j])

具体代码

#include
   
    using namespace std;int V[6] = {
   1,5,10,20,50,100};#define INF 0x3f3f3f3fint main(){
       int n, k, p;    cin >> n >> k >> p;    int minv1[1010] = {
   0};//minv1表示一次性买i张票所需的最小纸币数    int minv2[1010];//minv2表示买i张票所需的最小纸币数    fill(minv2,minv2+1010,INF);    minv2[0] = 0;    minv1[0] = 0;    for(int i = 1; i <= k; ++i){
    //贪心求出minv1        for(int val = i*p, j = 5 ; val ; --j){
               minv1[i] += val / V[j];            val %= V[j];        }    }    for(int i = 1; i <= n; ++i){
    //动态规划求出minv2        for(int j = 1; j <= min(i,k) ; ++j){
               minv2[i] = min(minv2[i],minv2[i-j] + minv1[j]);        }    }    cout << minv2[n]<< endl;    return 0;}
   

转载地址：http://qkhtz.baihongyu.com/