Codeforces ER16 710E
传送门：http://codeforces.com/problemset/problem/710/E
题目翻译
产生一个长度为n的全a字符串，增加/删除一个a消耗x时间，倍长当前字符串消耗y时间，求最短时间。
题解
可以发现，这是一个DP。然而删除操作并不是很方便DP。
我们仔细思考，发现减法的情况只可能在翻倍字符串之后出现一次。
首先我们不可能先添加一个字母再删除一个字母。
其次如果翻倍字符串需要两次减法，我们可以在翻倍之前做一次减法，这样次数更优。
综上，只有两种情况。当前需要产生n个字符时。
如果n为偶数，我们比较F[n/2]+y , F[n-1]+x
如果n为奇数，我们比较F[(n+1)/2]+x+y , F[n-1]+x
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #define LL long long using namespace std; const int Maxn=1e7; LL F[Maxn*2+5]; LL x,y; int n; LL Inf; LL dfs(int le){ if (le==0 || F[le]!=0) return F[le]; F[le]=Inf; F[le] = min(dfs(le-1)+x,(le&1)==0?dfs(le/2)+y:dfs((le+1)/2)+x+y); return F[le]; } int main(){ scanf("%d",&n); scanf("%I64d%I64d",&x,&y); F[0]=0; Inf=(LL)n*x+1LL; printf("%I64d\n",dfs(n)); return 0; } |
原文链接：Codeforces ER16 710E
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!