Codeforces 710 E. Generate a String (dp)-白红宇

Codeforces 710 E. Generate a String (dp)

阅读量：4322 次

发布时间：2019-06-06

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

题目链接：

加或者减一个字符代价为x，字符数量翻倍代价为y，初始空字符，问你到n个字符的最小代价是多少。

dp[i]表示i个字符的最小代价。

当i为偶数个的时候，由+1或者*2得到。

当i为奇数个的时候，由+1或者*2-1得到。

1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7 #include 
          
            8 #include 
           
             9 #include 
            
             10 #include 
             
              11 #include 
              
               12 #include 
               13 using namespace std;14 typedef __int64 LL;15 typedef pair 
                
                  P;16 const int N = 1e7 + 5;17 LL dp[N];18 19 int main()20 {21 int n;22 LL x, y;23 cin >> n >> x >> y;24 dp[1] = x;25 for(int i = 2; i <= n; ++i) {26 if(i&1) {27 dp[i] = min(dp[i - 1] + x, dp[i / 2 + 1] + x + y);28 } else {29 dp[i] = min(dp[i / 2] + y, dp[i - 1] + x);30 }31 }32 cout << dp[n] << endl;33 return 0;34 }