首页 > 代码库 > hdu--2191--终于可以说出dp水题这句话了-.-
hdu--2191--终于可以说出dp水题这句话了-.-
这题是 上一题的 recommend 过来的 很水..
虽然是多重背包 但是 因为数据太小了 完全可以不用二进制拆分去做
我两者都去写了下 ...都是0ms..
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 110; 7 int weight[size*20]; 8 int val[size*20]; 9 int dp[size];10 11 int main()12 {13 cin.sync_with_stdio(false);14 int t , n , m , cnt , a , b , c;15 cin >> t;16 while(t--)17 {18 cin >> n >> m;19 cnt = 0;20 memset( dp , 0 , sizeof(dp) );21 for( int i = 1 ; i<=m ; i++ )22 {23 cin >> a >> b >> c;24 for( int j = 1 ; j<=c ; j<<=1 )25 {26 val[cnt] = j * a;27 weight[cnt++] = j*b;28 c -= j;29 }30 if(c)31 {32 val[cnt] = c*a;33 weight[cnt++] = c*b;34 }35 }36 for( int i = 0 ; i<cnt ; i++ )37 {38 for( int j = n ; j>=val[i] ; j-- )39 {40 dp[j] = max( dp[j] , dp[ j-val[i] ] + weight[i] );41 }42 }43 cout << dp[n] << endl;44 }45 return 0;46 }
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 6 const int size = 110; 7 int weight[size*20]; 8 int val[size*20]; 9 int dp[size];10 11 int main()12 {13 cin.sync_with_stdio(false);14 int t , n , m , cnt , a , b , c;15 cin >> t;16 while(t--)17 {18 cin >> n >> m;19 cnt = 0;20 memset( dp , 0 , sizeof(dp) );21 for( int i = 1 ; i<=m ; i++ )22 {23 cin >> a >> b >> c;24 while(c--)25 {26 weight[cnt] = b;27 val[cnt++] = a;28 }29 }30 for( int i = 0 ; i<cnt ; i++ )31 {32 for( int j = n ; j>=val[i] ; j-- )33 {34 dp[j] = max( dp[j] , dp[ j-val[i] ] + weight[i] );35 }36 }37 cout << dp[n] << endl;38 }39 return 0;40 }
今天下午 网络赛 我要认真了 -.-
hdu--2191--终于可以说出dp水题这句话了-.-
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。