应室友要求贴代码：
#include <stdio.h> int main() { int n, k, p, i, j; scanf("%d %d %d",&n,&k,&p); int cost, note[10]={0}, all[1001]; for(i=0; i<10&&i<k; i++) { cost=p*(i+1); while(cost>=100){note[i]++;cost-=100;} while(cost>=50){note[i]++;cost-=50;} while(cost>=20){note[i]++;cost-=20;} while(cost>=10){note[i]++;cost-=10;} while(cost>=5){note[i]++;cost-=5;} while(cost){note[i]++;cost--;} } for(i=k; i<1001; i++) all[i]=999999; for(i=1; i<=n; i++) { if(i<=k) all[i]=note[i-1]; for(j=1; j<=10&&i-j>0&&j<=k; j++) { all[i]=all[i-j]+note[j-1]>all[i]?all[i]:all[i-j]+note[j-1]; } } //for(i=1; i<=n; i++) printf("%d\n",all[i]); printf("%d\n",all[n]); return 0; }
注意到这台售票机或许不能一下子买 $n$ 张票，所以直接贪心不可行。设 $a(i),i\le k$ 表示「一次」购买中买 $i$ 张票所需要的最少纸币数。这题中的货币面额成倍数关系所以可以直接用贪心，不然还是要动态规划。
有了 $a(i)$ 后，设 $dp(i)$ 表示总共买 $i$ 张票最少要花费的纸币数。假设分了好几次买票，分析最后一次买票的情况，根据买的张数不同，容易得到下列关系： $$ dp(0)=0 $$
$$ dp(i)=\min_{j=1}^{j\le\min(k,i)}(dp(i-k)+a(k)) $$
这个式子的复杂度是 $O(nk)$，对原题的数据量而言十分足够了。
#include "bits/stdc++.h" using namespace std; using u64 = uint64_t; int main() { u64 n, k, p; cin >> n >> k >> p; vector<u64> a(k + 1, 0); for (u64 i = 1; i <= k; ++i) { constexpr static u64 kParValue[6] = {1, 5, 10, 20, 50, 100}; for (u64 val = i * p, j = 5; val; --j) { a[j] += val / kParValue[j]; val %= kParValue[j]; } } vector<u64> dp(n + 1); dp[0] = 0; for (u64 i = 1; i <= n; ++i) { dp[i] = dp[i - 1] + a[i]; for (u64 j = 2; j <= min(i, k); ++j) { dp[i] = min(dp[i], dp[i - j] + a[j]); } } cout << dp[n] << '\n'; }
我的原代码中没有用 std::min，而写的是
std::min
auto const kTemp = xxx; if (elem > kTemp) { elem = kTemp; }
用这种 conditional move 的方法会比 min 的方法少一点分支判断，不过其实提升效果一般不明显，所以见仁见智了。
min
//状态：dp[i]表示当用k次确定使用的个数后，然后用得出的数据拼凑出i，所用的最少的个数 //dp[i]=min(dp[i-k]+vi[k]) #include <iostream> #include <vector> #include <string.h> #include <algorithm> using namespace std; int a[] = { 100,50,20,10,5,1 }; int n, k, p; vector<int> vi; int dp[1010]; int main() { fill(dp, dp + 1010, 100000000); cin >> n >> k >> p; for (int i = 1; i <= k; ++i) { int ans = 0; int j = 0; int _fnum = i * p; while (_fnum) { if (_fnum / a[j]) { ans = ans + _fnum / a[j]; _fnum = _fnum % a[j]; } ++j; if (a[j] == 0) { break; } } vi.push_back(ans); } dp[0] = 0; //todo for (int i = 1; i < 1010; ++i) { for (int j = 0; j < vi.size(); ++j) { if (i > j && dp[i - j - 1] != 100000000 && dp[i - j - 1] + vi[j] < dp[i]) { dp[i] = dp[i - j - 1] + vi[j]; } } } cout << dp[n] << endl; return 0; }
原来是完全背包问题的变式
水管切割问题，算出一次性买一张，两张…k张票各需要多少张纸币。 再将纸币数看成水管问题的权重就好，本质是求n进行切割使得总权重最小。
using namespace std;
int A[11]; int B[6] = {100,50,20,10,5,1}; int P[1010]; int num(int a) { int sum = 0; for(int i = 0;i < 6;i++) { sum += a/B[i]; a = a%B[i]; } return sum; } int main() { int n,k,p; cin >> n >> k >> p; for(int i = 1;i <= k;i++) { A[i] = num(i*p); P[i] = A[i]; } for(int i = k+1;i <= n;i++) P[i] = 10000000; for(int i = 2;i <= n;i++) { int Min = P[i]; for(int j = 1;j <= i;j++) { if(Min > P[j] + P[i-j]) Min = P[j] + P[i-j]; } P[i] = Min; } cout << P[n];
}
#include<bits/stdc++.h> #include<unordered_map> using namespace std; int yuan[] = { 100, 50, 20, 10, 5, 1}; int stuff[11]; int dp[1001]; int mount(int total) { int left, sum = 0; for (int i = 0; i < 6; i++) { left = total / yuan[i]; total = total % yuan[i]; sum += left; if (total == 0) break; } return sum; } int main() { int n, k, p; cin >> n >> k>> p; for (int i = 1; i <= k; i++) { int onceYuan = i * p; stuff[i] = mount(onceYuan); //完全背包中的物品 } fill(dp, dp + 1001, 1000000); dp[0] = 0; for (int i = 1; i <= n ; i++) { for (int j = 1; j <= k; j++) { if (j <= i) { dp[i] = min(dp[i], dp[i - j] + stuff[j]); } } } printf("%d\n", dp[n]); return 0; }
应室友要求贴代码：
[EOJ 3507] 坑爹的售票机 Easy
注意到这台售票机或许不能一下子买 $n$ 张票，所以直接贪心不可行。设 $a(i),i\le k$ 表示「一次」购买中买 $i$ 张票所需要的最少纸币数。这题中的货币面额成倍数关系所以可以直接用贪心，不然还是要动态规划。
有了 $a(i)$ 后，设 $dp(i)$ 表示总共买 $i$ 张票最少要花费的纸币数。假设分了好几次买票，分析最后一次买票的情况，根据买的张数不同，容易得到下列关系：
$$
dp(0)=0
$$
$$
dp(i)=\min_{j=1}^{j\le\min(k,i)}(dp(i-k)+a(k))
$$
这个式子的复杂度是 $O(nk)$，对原题的数据量而言十分足够了。
我的原代码中没有用
std::min，而写的是用这种 conditional move 的方法会比
min的方法少一点分支判断，不过其实提升效果一般不明显，所以见仁见智了。原来是完全背包问题的变式
水管切割问题，算出一次性买一张，两张…k张票各需要多少张纸币。
再将纸币数看成水管问题的权重就好，本质是求n进行切割使得总权重最小。
include
include
using namespace std;
int A[11];
int B[6] = {100,50,20,10,5,1};
int P[1010];
int num(int a)
{
int sum = 0;
for(int i = 0;i < 6;i++)
{
sum += a/B[i];
a = a%B[i];
}
return sum;
}
int main()
{
int n,k,p;
cin >> n >> k >> p;
for(int i = 1;i <= k;i++)
{
A[i] = num(i*p);
P[i] = A[i];
}
for(int i = k+1;i <= n;i++)
P[i] = 10000000;
for(int i = 2;i <= n;i++)
{
int Min = P[i];
for(int j = 1;j <= i;j++)
{
if(Min > P[j] + P[i-j])
Min = P[j] + P[i-j];
}
P[i] = Min;
}
cout << P[n];
}