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;
}
应室友要求贴代码:
思路分析
由于条件中该机器一次性最多能买k张票,因此将问题进行分解
1. 先算出在票数 <=k的范围内,买i张票所需的最小纸币数,用
minv1[]
存储,即对应于机器购买一次的情况,可用贪心算出。2. 当前需要买n张票,用
minv2[]
存储当前所需的最小纸币数,其中j的取值范围比较关键,我的理解是通过j的取值,与算出的minv1[]
进行关联,从而达到多次购票的效果,相应的动态转移方程为具体代码
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
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];
}
原来是完全背包问题的变式
水管切割问题,算出一次性买一张,两张…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];
}
可以把问题切割成两个背包问题,第一个是完全背包,求出各面值需要的票数.然后统计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;
}
[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
的方法少一点分支判断,不过其实提升效果一般不明显,所以见仁见智了。