POJ 1252 Euro Efficiency(最短路 完全背包)
2024-09-05 20:16:45
题意:
给定6个硬币的币值, 问组成1~100这些数最少要几个硬币, 比如给定1 2 5 10 20 50, 组成40 可以是 20 + 20, 也可以是 50 -10, 最少硬币是2个。
分析:
这道题可以转化成是一道最短路的方法去做, 设一开始的起点为0(什么硬币都不取), 然后每个点都有12条路(对应正负6种币值), 每条路的权值为1,
令dis[maxn]初始化为inf, 求出dis[1]~dis[100]即可。
但是最大值maxn要取比100更大, 比如 构造100的最优方法为51+51-1-1. 那么我们就需要102面值金钱的构造dist[102] 才能正确的推出dist[100], 虽然不知道这个最大值多少,但这个最大值取200可以过这题。
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;
const int maxn = ;
const int inf = 1e9;
int coin[];
int dis[maxn];
int vis[maxn];
void spfa(){
mem(vis);
queue<int> q;
fill(dis,dis+maxn, inf);
dis[] = ;
vis[] = ;
q.push();
while(!q.empty()){
int u = q.front();
for(int i = ; i < ; i++){
int v = u + coin[i];
if(v < || v > ) continue;//如果点v是负数, 那么不需要入队。
if(dis[v] > dis[u] + ){
dis[v] = dis[u] + ;
if(!vis[v]){
vis[v] = ;
q.push(v);
}
}
}
// vis[u] = 0; 这里其实不用标记, 因为每个点只会入队一次,边的权值都是1, 怎么扩展都是最短路
q.pop();
}
}
int main()
{
int t;
cin >> t;
while ( t -- ) {
for ( int i = ; i < ; ++ i ){
cin >> coin[ *i ];
coin[ * i + ] = -coin[ * i];//构造币值为负数的硬币
}
spfa();
double sum = 0.0;
int maxdis = ;
for ( int i = ; i <= ; ++ i ) {
sum += dis [i];
if ( dis[i] > maxdis )
maxdis = dis[i];
}
printf("%.2f %d\n",sum/100.0, maxdis);
}
return ;
}
最新文章
- Webstorm编译TypeScript
- 登录FTP,下载并读取文件内容
- 用花生壳实现内网映射,决解无域名、无公网IP、无服务器空间问题
- (转载)IO-同步、异步、阻塞、非阻塞
- IIS错误500.21
- Eclipse中出现Select at least one project解决办法
- JAVA的instanceOf什么时候用啊
- Chapter 15_2 编写模块的基本方法
- 聊一聊JQ中delegate事件委托的好处
- ajax请求获取实时数据
- freemind中内容变成html转义字符解决方法
- jQuery基础操作
- 炫龙炎魔T1笔记本 Win7 系统安装
- 百战程序员——JSP
- Python基础之条件语句和循环
- Vue插件plugins的基本操作
- IO流_文件切割与合并
- ASP.NET Core入门系列教程
- 20180925 SQL Server游标使用
- 05 面向对象:构造方法&;static&;继承&;方法 &;final