EOJ 3507 坑爹的售票机

问题描述

oxx 和 xjj 决定和小伙伴们一同坐船前往 Xiamen。去 Xiamen 的船票一张 p 元。

当他们满怀兴致地来到港口时发现居然只有不设找零的自动售票机，只能使用一元，五元，十元，二十元，五十元，一百元的纸币，且一次至多买 k 张船票。因此他们不得不去银行取钱。而 oxx 是个大懒人，他希望取的纸币数量越少越好，因此他想知道他们一行 n 人要都买到票至少需要取多少张纸币。
Input

第一行三个整数 n,k,p (1≤n≤10³,1≤k≤10,1≤p≤10³) 分别表示 oxx 需要购买船票张数，一次至多买船票数量，单张船票价格。
Output

输出一个整数，表示 oxx 至少要取多少张纸币。

题意即为：取钱n*p元，而一次至多取k张，问怎么取，使总共取的纸币张数最少

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #define INF 10e8
 4 #define C 1001
 5 const int m[6]={1,5,10,20,50,100};
 6 int min(int a,int b){return a>b?b:a;}
 7 int main()
 8 {
 9     int n,k,p,dp[C]={0},item[11]={0};
10     scanf("%d%d%d",&n,&k,&p);
11     for(int i=1;i<=k;i++)
12     {
13         int money=i*p;
14         for(int j=5;j>=0;j--)
15         {
16             item[i]+=money/m[j];
17             money%=m[j];
18         }
19     }
20     for(int i=n;i>=1;i--)dp[i]=INF;
21     for(int i=1;i<=k;i++)
22         for(int j=i;j<=n;j++)
23             dp[j]=min(dp[j-i]+item[i],dp[j]);
24 
25     printf("%d
",dp[n]);
26 
27     return 0;
28 }

首先求出买1-k张票需要多少张纸币,存入item数组中，

其中，下标i表示买i张票，item[i]，表示买一张票所需的张数，dp数组的下标i表示一共买i张票，dp[i]表示买i张票需要的最小纸币数

这样就转化成了完全背包问题：
　　有k种物品，每种物品都有无限个可取，每种物品i的价值是item[i]，容量是i,要求恰好放入一个容量为n的背包中，价值最小是多少？

因为要求价值最小，所以一开始便将dp数组每个元素初始化为INF。

状态转移方程就可以解释为：买j张票所需要的最小纸币张数，是“买[j-i]张票所需要的最小纸币张数加买i张票所需要的最小纸币张数”，与“买j张票所需要的最小纸币张数”这两者中的最小值。

21，22行的循环顺序以及一维数组的应用是一个空间优化，具体含义并不明确，只是套了个模板，有待学习。