贪心 + DFS-白红宇

贪心 + DFS

阅读量：6787 次

发布时间：2019-06-26

本文共 2995 字，大约阅读时间需要 9 分钟。

A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.

Your favorite store sells lemonade in bottles of n different volumes at different costs. A single bottle of type i has volume 2^i - 1 liters and costs c_i roubles. The number of bottles of each type in the store can be considered infinite.

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 ≤ 10⁹) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.

The second line contains n integers c₁, c₂, ..., c_n (1 ≤ c_i ≤ 10⁹) — 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.

Example

Input

4 12 20 30 70 90

Output

Input

4 3 10000 1000 100 10

Output

Input

4 3 10 100 1000 10000

Output

Input

5 787787787 123456789 234567890 345678901 456789012 987654321

Output

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.

题意：给你 n 个物品，以及一个容器的体积 l , n 个物品的体积是 2^i-1 ，求在超过容器体积的前提下，最小的花费是多少。

思路分析：想了一个贪心策略，优先去贪性价比最高的物品，当恰好装下的时候，此时可以记录一下答案，若不能时，此时可以让他们多装一个，再次记录一下答案，深搜就行了

代码示例：

/* * Author:  parasol  * Created Time:  2018/3/7 18:18:10 * File Name: 2.cpp */#include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   #include 
                    
                     using namespace std;#define ll long longconst ll maxn = 1e6+5;const double pi = acos(-1.0);const ll inf = 0x3f3f3f3f;struct node{ ll l, c; double p; bool operator< (const node &v)const{ return p < v.p; }}pre[35];ll n, l;ll ans = __LONG_LONG_MAX__;void dfs(ll x, ll cost, ll sum){ if (cost >= ans) return; if (sum <= 0) {ans = min(ans, cost); return;} if (x == n+1) return; ll f = sum / pre[x].l; int pt = 0; if (sum%pre[x].l == 0){ ans = min(ans, cost+f*pre[x].c); return; } else { dfs(x+1, cost+(f+1)*pre[x].c, sum-(f+1)*pre[x].l); pt = 1; } if (pt) { dfs(x+1, cost+f*pre[x].c, sum-f*pre[x].l); }}int main() { //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); cin >> n >> l; ll an = 1; for(ll i = 1; i <= n; i++){ scanf("%lld", &pre[i].c); pre[i].l = an; pre[i].p = 1.0*pre[i].c/an; an *= 2; } sort(pre+1, pre+1+n); dfs(1, 0, l); printf("%lld\n", ans); return 0;}

转载于:https://www.cnblogs.com/ccut-ry/p/8525643.html

你可能感兴趣的文章