首页 > 代码库 > CodeForces 710E Generate a String
CodeForces 710E Generate a String
$SPFA$，优化，$dp$。
写了一个裸的$SPFA$，然后加了一点优化就过了，不过要$300$多$ms$。
$dp$的话跑的就比较快了。
$dp[i]$表示输入$i$个字符的最小花费。
首先$dp[i]=dp[i-1]+x$。
其次，如果$i$是个偶数，那么$dp[i]$还可以从$dp[\frac{i}{2}]$推过来。
如果$i$是奇数，那么$dp[i]$还可以从$dp[\frac{i}{2}]$和$dp[\frac{i}{2} + 1]$推过来。
$SPFA$：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}int n;LL x,y;LL a[10000010];bool f[10000010];int main(){ scanf("%d%lld%lld",&n,&x,&y); memset(a,-1,sizeof a); a[0]=0; a[n]=n*x; queue<int>Q; Q.push(0); f[0]=1; while(!Q.empty()) { int h=Q.front(); Q.pop(); f[h]=0; if(h+1<=n) { if(a[h+1]==-1||a[h]+x<a[h+1]) { a[h+1]=a[h]+x; if(f[h+1]==0) { Q.push(h+1); f[h+1]=1; } } } if(h-1>=0) { if(a[h-1]==-1||a[h]+x<a[h-1]) { a[h-1]=a[h]+x; if(f[h-1]==0) { Q.push(h-1); f[h-1]=1; } } } LL cost=min(h*x,y); if(2*h<=n) { if(a[2*h]==-1||a[h]+cost<a[2*h]) { a[2*h]=a[h]+cost; if(f[2*h]==0) { Q.push(2*h); f[2*h]=1; } } } else { if(a[n]==-1) a[n]=a[h]+y+x*(2*h-n); else a[n]=min(a[n],a[h]+y+x*(2*h-n)); } } printf("%lld\n",a[n]); return 0;}
$dp$：
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-8;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}int n; LL x,y,dp[10000010];int main(){ scanf("%d%lld%lld",&n,&x,&y); for(int i=1;i<=n;i++) { dp[i]=dp[i-1]+x; if(i%2==0) dp[i]=min(dp[i],dp[i/2]+y); else { dp[i]=min(dp[i],dp[i/2+1]+y+x); dp[i]=min(dp[i],dp[i/2]+x+y); } } printf("%lld\n",dp[n]); return 0;}
CodeForces 710E Generate a String
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。