P2725 USACO3.1邮票 stamps题解
发布时间
阅读量：
阅读量
目录
-
- 问题陈述
- 问题解析
- 程序代码
- 问题陈述
题面
题目分析
这实际上是一种完全背包问题。
可以将当前的邮资数值 i 视作背包的容量，每一种邮票则对应一个物品，而邮票的面值相当于该物品所占据的体积，其中 k 用于限制所选物品的数量上限。
在判断所使用邮票数量处于允许范围内的前提下，选择更小的数值作为结果。
对应的状态转移公式为 f[j]=min(f[j],f[j-x]+1)。
最终只需从前往后进行搜索即可得出答案。
code
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int k,n,ans;
int f[2000039];
int main(){
scanf("%d%d",&k,&n);
register int i,j;
for(i=1;i<=2000000;i++)
f[i]=0x7fffffff;
f[0]=0;
int x;全部评论 (0)
还没有任何评论哟~