3507. 坑爹的售票机 (Easy)

10175102262 LarsPendragon

应室友要求贴代码:

#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;
}
Deuchie

[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)$,对原题的数据量而言十分足够了。

#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,而写的是

auto const kTemp = xxx;
if (elem > kTemp) {
    elem = kTemp;
}

用这种 conditional move 的方法会比 min 的方法少一点分支判断,不过其实提升效果一般不明显,所以见仁见智了。

cd106224
//状态: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;
}
150042

原来是完全背包问题的变式

Twisted9

水管切割问题,算出一次性买一张,两张…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];

}

Money4
#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;
}
你当前正在回复 博客/题目
存在问题!