首页 > 代码库 > zoj 1558 - Euro Efficiency
zoj 1558 - Euro Efficiency
题目:给你6中面值的货币,统计组成1~100面值需要的最小平均货币数量,以及所有值中使用最多货币的数量。
分析:dp,搜索,松弛迭代。6种货币面值可能有负的。
解法1:可利用利用完全背包求解;
因为货币可能为负,所以可能是与超过100的面值“相加”的结果,所以扩大容量即可;
解法2:利用松弛迭代,松弛每种货币的使用基础货币的数量,不能更新即可;
使用bfs从6种基础货币开始搜索,数量已定位递增,每个面值找到时一定是组成最少的;
扩展半径控制到100(0~300)即可。
说明:(2011-09-19 10:06)。
背包解法:
#include <stdio.h> #include <iostream> using namespace std; int F[ 205 ]; int C[ 7 ]; int main() { int T; while ( ~scanf("%d",&T)) while ( T -- ) { for ( int i = 1 ; i <= 6 ; ++ i ) scanf("%d",&C[ i ]); for ( int i = 0 ; i <= 200 ; ++ i ) F[ i ] = i; for ( int k = 0 ; k <= 100 ; ++ k ) for ( int i = 6 ; i >= 1 ; -- i ) { for ( int j = 200 ; j >= C[ i ] ; -- j ) if ( F[ j ] > F[ j-C[ i ] ] + 1 ) F[ j ] = F[ j-C[ i ] ] + 1; for ( int j = 0 ; j <= 200-C[ i ] ; ++ j ) if ( F[ j ] > F[ j+C[ i ] ] + 1 ) F[ j ] = F[ j+C[ i ] ] + 1; } int Sum = 0,Max = 0; for ( int i = 1 ; i <= 100 ; ++ i ) { Sum += F[ i ]; if ( Max < F[ i ] ) Max = F[ i ]; } printf("%d.%d %d\n",Sum/100,Sum%100,Max); } return 0; }松弛解法:
#include<iostream> #include<cstdlib> using namespace std; int coin[ 6 ]; int sign[ 301 ]; int leat[ 301 ]; int queu[ 301 ]; int main() { int t; cin >> t; while ( t -- ) { for ( int i = 0 ; i < 6 ; ++ i ) cin >> coin[ i ]; memset( sign , 0 , sizeof( sign ) ); for ( int i = 0 ; i < 6 ; ++ i ) { sign[ coin[ i ]+100 ] = 1; leat[ coin[ i ]+100 ] = 1; queu[ i ] = coin[ i ]+100; } int move = 0,save = 6; while ( move < save ) { int p = queu[ move ]; for ( int k = 0 ; k < 6 ; ++ k ) { /* 增加 */ int q = p + coin[ k ]; if ( q >= 0 && q < 301 && !sign[ q ] ) { sign[ q ] = 1; queu[ save ++ ] = q; leat[ q ] = leat[ p ] + 1; } /* 减少 */ q = p - coin[ k ]; if ( q >= 0 && q < 301 && !sign[ q ] ) { sign[ q ] = 1; queu[ save ++ ] = q; leat[ q ] = leat[ p ] + 1; } } ++ move; } double sum = 0.0; int max = 0; for ( int i = 101 ; i < 201 ; ++ i ) { sum += leat[ i ]; if ( leat[ i ] > max ) max = leat[ i ]; } printf("%.2f %d\n",sum/100.0,max); } return 0; }
zoj 1558 - Euro Efficiency
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。