Problem #3507 - ECNU Online Judge

4 年，11 月前

应室友要求贴代码：

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

回复 6 0

JamesHuang77

1 年，10 月前

思路分析

由于条件中该机器一次性最多能买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<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;
}

回复 4 0

Twisted9

3 年前

水管切割问题，算出一次性买一张，两张…k张票各需要多少张纸币。
再将纸币数看成水管问题的权重就好，本质是求n进行切割使得总权重最小。

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];

}

回复 0 0

pillvic

2 年前

可以把问题切割成两个背包问题,第一个是完全背包,求出各面值需要的票数.然后统计1到限制票所需的钞票数,第二个也是完全背包(老鲁迅了),求出指定票数需要的钞票数

include

using namespace std;
const int LEN=10001;
const int inf=0x3fffffff;
const int tnum=1001;
int dp[LEN];
int dp2[tnum];
int cost2[11];
int value[6]={1,5,10,20,50,100};
int main(){
ios::sync_with_stdio(false);
int ticketNum, limitNum,price;
cin>>ticketNum>>limitNum>>price;
int capacity = limitNumprice;
fill(dp,dp+LEN,inf);
dp[0] = 0;
for(int i=0;i<6;i++) dp[value[i]]=1;
for(int i=0;i<6;i++){
for(int v=value[i];v<=capacity;v++){
dp[v] = min(dp[v], dp[v-value[i]]+dp[value[i]]);
}
}
//cost2[i]:money num of buy i tickets
for(int i=0;i<=limitNum;i++)cost2[i] = dp[iprice];
//dp2[i]:buy i tickets at least need
fill(dp2,dp2+tnum, inf);
dp2[0] = 0;
for(int i=1;i<=limitNum;i++){
for(int v=i;v<=ticketNum;v++){
dp2[v] = min(dp2[v],dp2[v-i]+cost2[i]);
}
}
cout<<dp2[ticketNum]<<”\n”;
return 0;
}

回复 0 0

10175101178

1 年，10 月前

include

define max(a,b) ((a) > (b) ? (a) : (b))

define min(a,b) ((a) < (b) ? (a) : (b))

define N 7

define M 10005

define INF 0X3F3F3F3F

int dp[N][M];
int main()
{
/我这个DP思路特别简单，就是在使用i硬币的时候，考虑选和不选两种情况，就是在一个购票最大范围内/
int n,k,p;
scanf(“%d %d %d”,&n,&k,&p);
int product=kp;
int v[7]={0,1,5,10,20,50,100};
/初始化，6种硬币，购买金额为0，需要的最小数量/
for(int i=0;i<N;i++) {
dp[i][0] = 0;
dp[i][1] =1;
}
/初始化，0，1号硬币，购买金额为1-M，需要的最小数量*/
for(int j=1;j<M;j++){
dp[0][j]=INF;
dp[1][j]=j;}
for(int i=1;i<N;i++)
for(int j=1;j<=product;j++)
if(j-v[i]>=0)
dp[i][j]=min(dp[i-1][j],dp[i][j-v[i]]+1);
else
dp[i][j]=dp[i-1][j];

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]);

}

回复 0 0

Money4

2 年，11 月前

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

回复 0 0

cd106224

2 年，12 月前

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

回复 0 0

150042

4 年，10 月前

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

回复 0 0

Fifnmar

2 年，10 月前

[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 的方法少一点分支判断，不过其实提升效果一般不明显，所以见仁见智了。

回复 1 1

3507. 坑爹的售票机 (Easy)

思路分析

具体代码

include

include

include

include

include

include

define max(a,b) ((a) > (b) ? (a) : (b))

define min(a,b) ((a) < (b) ? (a) : (b))

define N 7

define M 10005

define INF 0X3F3F3F3F

[EOJ 3507] 坑爹的售票机 Easy

服务

开源

关于我们