codeforces 710E Generate a String(简单dp)

传送门：http://codeforces.com/problemset/problem/710/E

分析：让你写一个全由"a"组成的长为n的串，告诉你两种操作，第一种：插入一个字母或者删除一个字母需要花费ｘ秒，

第二种：复制现有的串，并加入到原来的穿上，花费ｙ秒，问你最少花费多少时间？　用dp[i]表示需要花费的最少时间，‘

然后对i为偶数的情况取min(dp[i-1] +x,dp[i/2]+y),当i为奇数时min(dp[i-1] + x, min(dp[i/2+1] + y + x,dp[i/2] + y + x))。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn = 1e7+;

 ll dp[maxn];

 int main()

 {

     ios::sync_with_stdio(false);

     cin.tie();

     int n,x,y;

     cin >> n >> x >> y;

     memset(dp,,sizeof(dp));

     for(int i = ;  i<= n; i++)

     {

         if(i&)

             dp[i] = min(dp[i-] + x, min(dp[i/+] + y + x,dp[i/] + y + x));

         else

             dp[i] = min(dp[i/] +y, dp[i-] +x);

     }

     cout << dp[n] << endl;

     return ;

 }

巴特西

codeforces 710E Generate a String(简单dp)

最新文章

热门文章