- You want to buy at least L liters of lemonade. How many roubles do you have to spend?
- Input
- The first line contains two integers n and L (1?≤?n?≤?30; 1?≤?L?≤?1e9) - the number of types of bottles in the store and the required amount of lemonade in liters, respectively.
- The second line contains n integers c1,?c2,?...,?cn (1?≤?ci?≤?1e9) - the costs of bottles of different types.
- Output
- Output a single integer - the smallest number of roubles you have to pay in order to buy at least L liters of lemonade.
- SampleInput 1
- 4 12
- 20 30 70 90
- SampleOutput 1
- 150
- SampleInput 2
- 4 3
- 10000 1000 100 10
- SampleOutput 2
- 10
- SampleInput 3
- 4 3
- 10 100 1000 10000
- SampleOutput 3
- 30
- SampleInput 4
- 5 787787787
- 123456789 234567890 345678901 456789012 987654321
- SampleOutput 4
- 44981600785557577
- Note
- In the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles.
- In the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.
- In the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.
- if(vids[i] == 1){
- dp2[i] = min(dp2[i - 1] + dp[i - 1] * 2, dp2[i - 1] + dp[i]);
- }
- else{
- dp2[i] = min(dp2[i - 1], dp[i]);
- }
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- using namespace std;
- const int MAXN = 35;
- long long dp[MAXN], arr[MAXN], dp2[MAXN];
- int vids[MAXN];
- int main(){
- iOS::sync_with_stdio(false);
- int n, k;
- cin>> n>> k;
- for(int i = 1; i <= 32; i ++){
- arr[i] = __LONG_LONG_MAX__;
- }
- for(int i = 1; i <= n; i ++){
- cin>> arr[i];
- }
- dp[1] = arr[1];
- for(int i = 2; i <= 32; i ++){
- dp[i] = min(arr[i], dp[i - 1] * 2);
- }
- for(int i = 32 - 1; i>= 1; i --){
- dp[i] = min(dp[i], dp[i + 1]);
- }
- int num = 1;
- while(k){
- if(k & 1) vids[num] = 1;
- num ++;
- k>>= 1;
- }
- if(vids[1] == 1) dp2[1] = dp[1];
- else{
- dp2[1] = 0;
- }
- for(int i = 2; i <= 32; i ++){
- if(vids[i] == 1){
- dp2[i] = min(dp2[i - 1] + dp[i - 1] * 2, dp2[i - 1] + dp[i]);
- }
- else{
- dp2[i] = min(dp2[i - 1], dp[i]);
- }
- }
- cout << dp2[32] << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3218980.html