LeetCode 4 Keys Keyboard
Imagine you have a special keyboard with the following keys:
Key 1: (A)
: Prints one 'A' on screen.
Key 2: (Ctrl-A)
: Select the whole screen.
Key 3: (Ctrl-C)
: Copy selection to buffer.
Key 4: (Ctrl-V)
: Print buffer on screen appending it after what has already been printed.
Now, you can only press the keyboard for N times (with the above four keys), find out the maximum numbers of 'A' you can print on screen.
Example 1:
Input: N = 3 Output: 3 Explanation: We can at most get 3 A's on screen by pressing following key sequence: A, A, A
Example 2:
Input: N = 7 Output: 9 Explanation: We can at most get 9 A's on screen by pressing following key sequence: A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V
Note:
- 1 <= N <= 50
- Answers will be in the range of 32-bit signed integer.
给定四个按键,有四种操作:
- A: 打印一个字符A
- Ctrl-A: 全选
- Ctrl-C: 复制
- Ctrl-V: 粘贴
问通过n次按键操作,最多可以打印出多少个字符。
稍微分析一下,增加字符比较快的方法是用Ctrl-V,连带着需要Ctrl-C和Ctrl-A的配合,所以要想快速增加字符,必须要以Ctrl-A, Ctrl-C, Ctrl-V结尾,这就需要3个操作。当n比较小时,这3个操作相对来说比较耗时,通过分析可知,当N<=6时,直接用N次Print(A)操作能得到最多的字符。
假设dp[i]表示使用i次操作能得到的最多字符,显然dp[i]=i,当i<=6时。
当i>6时,我们可以考虑用Ctrl-A, Ctrl-C, Ctrl-V,所以结尾我们至少要空出3个操作来使用技能,也就是我们最多只能在i-3的地方开始释放Ctrl-A, Ctrl-C, Ctrl-V技能,假设释放技能的位置是b,则b<=i-3;下界是我们可以在一开始只有一个字符时使用技能,即b>=1。所以我们遍历[1,i-3]的地方释放技能,则我们可以有i-b-2个Ctrl-V结尾,再加上释放技能的位置已经有一个dp[b]了,所以总字符数是dp[b]*(i-b-1)。使用贪心策略求最大值。
完整代码如下:
class Solution { public: int maxA(int N) { if (N <= 6)return N; vector<int> dp(N + 1, 0); for (int i = 1; i <= 6; ++i)dp[i] = i; for (int i = 7; i <= N; ++i) { for (int b = i - 3; b >= 1; --b) { dp[i] = max(dp[i], dp[b] + dp[b] * (i - b - 2)); } } return dp[N]; } };
本代码提交AC,用时0MS。