首页 > 代码库 > codeforces 710E Generate a String(简单dp)
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))。
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 1e7+7; 5 ll dp[maxn]; 6 7 int main() 8 { 9 ios::sync_with_stdio(false);10 cin.tie(0);11 int n,x,y;12 cin >> n >> x >> y;13 memset(dp,0,sizeof(dp));14 for(int i = 1; i<= n; i++)15 {16 if(i&1)17 dp[i] = min(dp[i-1] + x, min(dp[i/2+1] + y + x,dp[i/2] + y + x));18 else19 dp[i] = min(dp[i/2] +y, dp[i-1] +x);20 }21 cout << dp[n] << endl;22 return 0;23 }
codeforces 710E Generate a String(简单dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。