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. 1 <= N <= 50
2. 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)。使用贪心策略求最大值。 完整代码如下： [cpp] 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]; } }; [/cpp] 本代码提交AC，用时0MS。]]>