3507. 坑爹的售票机 (Easy)

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

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

#include<bits/stdc++.h>
using namespace std;
int V[6] = {1,5,10,20,50,100};
#define INF 0x3f3f3f3f
int 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;
}

//状态：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;
}

int a[k+1];
for(int j=0;j<(k+1);j++){
    a[j]=dp[6][p*j];
}
int x[1005];
x[0]=0;
for(int i=1;i<1005;i++)
    x[i]=INF;
for(int i=1;i<=n;i++){
    for(int j=1;j<=min(i,k);++j)
        x[i]=min(x[i],x[i-j]+a[j]);
}

printf("%d",x[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;
}

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

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