首页 > 代码库 > Codeforces 710 E. Generate a String (dp)
Codeforces 710 E. Generate a String (dp)
题目链接：http://codeforces.com/problemset/problem/710/E
加或者减一个字符代价为x，字符数量翻倍代价为y，初始空字符，问你到n个字符的最小代价是多少。
dp[i]表示i个字符的最小代价。
当i为偶数个的时候，由+1或者*2得到。
当i为奇数个的时候，由+1或者*2-1得到。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef __int64 LL;15 typedef pair <int, int> 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 }
Codeforces 710 E. Generate a String (dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。