LeetCode 4 Keys Keyboard

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)。使用贪心策略求最大值。

完整代码如下:

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。

Leave a Reply

Your email address will not be published. Required fields are marked *