两道倍数codeforces 题 —— 2倍与加减1相关

• 题目大意
  • 题1
  • 题2
• 思路
  • 题1
  • 题2
• 总结

题目大意

题1

一个设备可支持两种操作：
将当前数 \times 2 。
将当前数 -1−1 。
另外，当设备中的数不是正数时，设备将会崩溃。
现在给出两个数 n,m ，问你需要多少次操作才能将 n 变成 m 。

题2

给定正整数 n, x, y，你要生成一个长度为 n 的字符串，有两种操作：
添一字符或删去一个原有字符，代价为 x；
将已有字串复制粘贴一次（翻倍），代价为 y。
求最小代价。

思路

题1

1，让我们先来看第一题
要让我们分类讨论。因为都是正数

1. 所以当 n>m 时，只有n--才可以到达m。 这个时候是不可能再有n*2这个步骤的
2. 当n<m时。n*2 与 n-- 难于判断，正难则反
   若需要将 m->n ，则说明啥，m可以除2时，就除以2，如果不能，那我就再加1，然后除2。只有这两个步骤才能到达n
   那存不存在 我先加两次1，然后再除以2，那肯定没有必要啊，这个操作数会大于 n/2 再加1 的两次操作
   明显贪心

题2

第2题，题目是：
0->n 其中inc/dec 为 x代价 =2 为 y代价
跟1题的不同点在于
1，0<n
2, 可以加1，也可以减1
跟第1题相比，明显这题是使用dp，而且很容易陷入完全背包解法。而实际上可以利用：2可以分两种情况讨论，当i为偶数/奇数时
偶数：dp[i] = max(dp[i/2]+y,dp[i-1]+x);
奇数：dp[i] = max(dp[(i+1)/2]+x+y,dp[i-1]+x);
其它情况，代价更高，故不需要考虑。

总结

当看到 *=2, +-1 这些条件时，就需要想到通过奇偶去分别讨论。