首页 > 代码库 > hdu 2546 - 饭卡
hdu 2546 - 饭卡
题目:电子科大本部食堂的饭卡有一种很诡异的设计,即在购买之前判断余额。如果购买一个商品之前,
卡上的剩余金额大于或等于5元,就一定可以购买成功(即使购买后卡上余额为负),
否则无法购买(即使金额足够)。所以大家都希望尽量使卡上的余额最少。某天,食堂中有n种菜出售,
每种菜可购买一次。已知每种菜的价格以及卡上的余额,问最少可使卡上的余额为多少。
分析:dp,01背包。 枚举最后卖的一盘菜,其他的01背包到m-5的最大值即可。
如果直接背包的话 T(n)= 1000^3 肯定TLE;
将枚举的状态从1-1000转移到1-50(只有50种价格),然后对每种物品(价格)二进制拆分;
T(n)= 1250 0000。
说明:(2011-09-19 07:51)。
#include <iostream> #include <cstdlib> using namespace std; int F[ 1002 ]; int W[ 1002 ]; int C[ 52 ]; int T[ 52 ]; int main() { int n,m,w; while ( cin >> n && n ) { for ( int i = 1 ; i <= 50 ; ++ i ) C[ i ] = 0; for ( int i = 1 ; i <= n ; ++ i ) { cin >> w; ++ C[ w ]; } cin >> m; int min = m; for ( int i = 1 ; i <= 50 ; ++ i ) { if ( !C[ i ] ) continue; for ( int j = 1 ; j <= 50 ; ++ j ) T[ j ] = C[ j ]; -- T[ i ]; //二进制拆分 int Count = 1; for ( int j = 1 ; j <= 50 ; ++ j ) { int two = 1; while ( two < T[ j ] ) { W[ Count ++ ] = j*two; T[ j ] -= two; two *= 2; } if ( T[ j ] ) W[ Count ++ ] = j*T[ j ]; } for ( int j = 0 ; j <= m ; ++ j ) F[ j ] = 0; for ( int j = 1 ; j < Count ; ++ j ) for ( int k = m ; k >= W[ j ] ; -- k ) if ( F[ k ] < F[ k-W[ j ] ]+W[ j ] ) F[ k ] = F[ k-W[ j ] ]+W[ j ]; if ( m >= 5 && min > m-F[ m-5 ]-i ) min = m-F[ m-5 ]-i; } cout << min << endl; } return 0; }
hdu 2546 - 饭卡
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。