[CF710E] Generate a String - dp,结论
Description
给定正整数 n,x,y,生成一个长度为 n 的字符串,有两种操作:添加或者删除一个字符代价为 x;将已有的字串翻倍代价为 y,求生成任意一个长度为 n 的字符串的最小代价。
Solution
性质:删除操作一定不会连续进行超过一次
所以我们把删除的情况手工枚举了,这样转移的拓扑结构就变成线性的了
具体地,当 i 是偶数时,转移来源为 \(i-1, \frac i 2\)
当 i 时奇数时,转移来源为 \(i-1, \frac {i+1} 2\)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 10000005;
int f[N];
int n, x, y;
signed main()
{
ios::sync_with_stdio(false);
cin >> n >> x >> y;
for (int i = 1; i <= n; i++)
{
if (i & 1)
f[i] = min(f[i - 1] + x, f[(i + 1) / 2] + x + y);
else
f[i] = min(f[i - 1] + x, f[i / 2] + y);
}
cout << f[n] << endl;
}