CF710E Generate a String 题解

· · 题解

可能更好的阅读体验

题目传送门

题目大意

你需要通过以下操作生成一个长度为 n 的字符串：

  1. 在字符串末尾添加一个字符，代价为 x。
  2. 将整个字符串复制一遍添加在后面，代价为 y。

求最小代价。

1\le n\le 10^7$，$1\le x,y\le 10^9

题目解析

看似可以贪心并且很难找到正确解法，又可以搜索，显然是 DP。
设 f_i 为生成长度为 i 的字符串的代价。 根据题目可以列出转移方程;

f_i=\left\{ \begin{aligned} & \min\{f_{i-1}+x,f_{i+1}+x\} & & x\text{为奇数} \\ & \min\{f_{i-1}+x,f_{i+1}+x,f_{i/2}+y\} & & x\text{为偶数} \end{aligned} \right.

但是我们会发现，这样列出来的 DP 式是有环的，不能快速转移。我们考虑将 DP 式中的 f_{i+1}+x 这一项替换掉。

首先考虑 i 为偶数的情况。
如果从 i+1 转移过来得到答案，那么显然此时 i+1 是由 i+2 转移来的。此时我们连续执行了两次减一操作。显然我们可以先减一在乘二，所以这样肯定不优，因此 i 为偶数的时候就没必要从 i+1 转移了。
然后考虑 i 为奇数。
如果从 i+1 转移，那么显然 i+1 肯定是由 (i+1)/2 转移得来的，因为偶数不可能从更大的数字减一得到。

这样 DP 式就变成了

f_i=\left\{ \begin{aligned} & \min\{f_{i-1}+x,f_{(i+1)/2}+x+y\} & & x\text{为奇数} \\ & \min\{f_{i-1}+x,f_{i/2}+y\} & & x\text{为偶数} \end{aligned} \right.

此时就可以直接 O(n) 转移了。

int n; ll x,y,f[maxn]; 
int main(){
    n=read(); x=read(); y=read(); int i; f[1]=x;
    for(i=2;i<=n;i++)
        if(i&1) f[i]=mmin(f[i-1]+x,f[(i+1)>>1]+x+y); 
        else f[i]=mmin(f[i-1]+x,f[i>>1]+y);
    print(f[n]); return 0;
}