AcWing 4805. 加减乘
原题链接
困难
作者:
我是java同学
,
2023-02-05 20:30:54
,
所有人可见
,
阅读 182
dp 递归
- 正难则反:题意变成把
n
变为0
- 性质1:加减不能相连
- 性质2:加不能连续(以下证明)
- 集合:将
i
变成0
的最小代价
-
边界
:当i = 1
时,i + 1 / 2
不变,但初始化f为正无穷可以避免边界情况
- 类似题目:抓住那头牛
#include <iostream>
using namespace std;
const int N = 10000010;
typedef long long LL;
LL n, x, y;
LL dfs(LL u)//从n减到0
{
if (u == 1) return x;//前两行是递归边界
if (u == 2) return x + min(x, y);//可以先除再减,也可以减两次
if (u % 2 == 0) //偶数(除2、减2)
return dfs(u / 2) + min(y, x * u / 2);
else //奇数(加1、减1)
return x + min(dfs(u - 1), dfs(u + 1));
}
int main()
{
scanf("%lld%lld%lld", &n, &x, &y);
cout << dfs(n) << endl;
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 10000010;
int n;
int x, y;
LL f[N];
int main()
{
scanf("%d%d%d", &n, &x, &y);
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= n; i ++ )
if (i % 2)
f[i] = min(f[(i + 1) / 2] + x + y, f[i - 1] + x);
else
f[i] = min(f[i / 2] + y, f[i - 1] + x);
printf("%lld\n", f[n]);
}