首页 > 代码库 > （DP）codeforces - 710E Generate a String
（DP）codeforces - 710E Generate a String
原题链接：http://www.codeforces.com/problemset/problem/710/E
题意：一个字符串，开始长度为0，目标长度为n，长度+1或-1需要的时间为x，长度*2需要的时间为y，求0到m需要的最少时间。
分析：这题一上来直接写优先队列bfs，然后很愉快的超内存的了。就想别的方法，想了一会没想清晰，感觉可以用记忆化搜索，就往这上面一想，才发现直接dp就行了。
可以很容易发现，奇数肯定是+1或者通过*2逼近并且+1或-1得到。
而偶数只能在+1和翻倍得到。
所以在奇数情况下的状态转移方程为dp[i]=min(dp[i-1]+x,dp[i/2]+x+y,dp[i/2+1]+x+y)
偶数情况下的为dp[i]=min(dp[i-1]+x,dp[i/2]+y)
代码：
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<set>#include<vector>#include<queue>#include<map>#include<list>#include<bitset>#include<string>#include<cctype>#include<cstdlib>using namespace std;typedef long long ll;typedef unsigned long long ull;namespace Math {//最大公约数ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b);}//欧拉素数筛int Euler_prime(int *prime, bool *vis, int maxn) { memset(vis, true, sizeof(vis)); int tot = 0; for (int i = 2; i < maxn; i++) { if (vis[i]) prime[tot++] = i; for (int j = 0; j < tot&&prime[j] * i < maxn; j++) { vis[i*prime[j]] = false; if (i%prime[j] == 0) break; } } return tot;}}const int inf = 1 << 30;const ll lnf = 1ll << 60;//-----upstair is template------//const int maxn=1e7;ll dp[maxn];void solve() { int n,x,y; scanf("%d%d%d",&n,&x,&y); fill(dp,dp+maxn,lnf); dp[0]=0; for(int i=1;i<=n;i++){ if(i&1){ dp[i]=min(dp[i-1]+x,min(dp[i/2+1]+x+y,dp[i/2]+x+y)); } else{ dp[i]=min(dp[i-1]+x,dp[i/2]+y); } } printf("%I64d\n",dp[n]);}int main() {#ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout);#endif //iostream::sync_with_stdio(false); solve(); return 0;}
（DP）codeforces - 710E Generate a String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。