键盘特殊_特殊键盘

妖狐艹你老母 2023-03-05 08:29 2阅读 0赞

键盘特殊

**Problem statement:**

**问题陈述：**

Imagine you have a special keyboard with four types of keys:

想象一下，您有一个特殊的键盘，其中包含四种类型的键：

Key 1: Prints 'I' on screen

按键1：在屏幕上打印“ I”

Key 2: Select whatever printed in screen

键2：选择屏幕上打印的任何内容

Key 3: Copy selection to buffer

关键3：将选择复制到缓冲区

Key 4: Append buffer on-screen after what has already been printed. If you can only press the keyboard for N times (with the above four keys), write a program to produce maximum numbers of I's possible to be printed on the screen.

关键4：在已打印的内容之后在屏幕上追加缓冲区。 如果您只能按键盘N次(使用上述四个键)，请编写一个程序以产生最大数量的I(可以在屏幕上打印)。

**Input:**

**输入：**

Input is ***N***, number of times keys can be pressed in total.

输入为***N*** ，总共可以按键的次数。

**Output:**

**输出：**

Print maximum number of I's possible to print

打印我可以打印的最大数量

**Constraints:**

**限制条件：**

1 ≤ N ≤ 75

**Example:**

**例：**

Input:
    2
    
    Output:
    2
    
    Explanation:
    We can at most get 2 I's on screen by pressing 
    following key sequence Key1, key1.
    Pressing other keys have no effect. 
    Like key 1, key2 will produce only one I on screen. 
    
    Input:
    7
    
    Output:
    9
    
    Explanation:
    We can at most get 9 I's on screen by pressing 
    following key sequence.
    Key1, Key1, Key1, Key2, Key3, key4, Key4
    
    I //after pressing key1
    I I  //again pressing key 1
    I I I //again pressing key1
     
    I I I //pressing key2 selects three I's
    I I I // pressing key3 copies these three I's to buffer
    I I I I I I // pressing key4 appends these three I's 
    I I I I I I I I I // pressing key4 again appends these three I's

**Solution Approach:**

**解决方法：**

Basically,

基本上，

Two things need to be understood to solve this problem

解决此问题需要了解两点

***Key4*** appends whatever is printed already on screen before 3 key pressing

按下3键之前， ***Key4会***附加屏幕上已经打印的内容

That means at moment 4,

这意味着在第四时刻

You can append whatever was printed while moment 1 as to print in moment 4, you need to press ***key2*** at moment 2 and ***key3*** at moment 3.

您可以在第1时刻添加要在第4时刻打印的内容，然后在第2时刻按***key2*** ，在第3时刻按***key3*** 。

So, the recursive function can be written as

因此，递归函数可以写成

Let,

让，

***F(n) ***= max number of I’s printed on screen

***F(n)*** =我在屏幕上打印的最大数量

So, for ***n>3***

因此，对于***n> 3***

F(n) = max(f(j)*(n-j-1)) for 1<=j<=n-3
    
    Where, 
    F(j) = already printed characters up to moment j 
    and (n-j-1) is number of appending possible

So, now we need to convert the recursion into DP.

因此，现在我们需要将递归转换为DP。

1)  Initialize dp[n+1] like following base value;
    2)  for i=0 to n
            dp[i]=i;
    3)  Fill the DP table
            for i=4 to n
                for j=i-3 to 1,j--
                    dp[i]=max(dp[i],dp[j]*(i-j-1));
                end for
            End for
    4)  Return dp[n]

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    int specialKeyboard(int n)
    {
    
        int dp[n + 1];
        for (int i = 0; i <= n; i++)
            dp[i] = i;
    
        for (int i = 6; i <= n; i++) {
            for (int j = i - 3; j >= 1; j--) {
                dp[i] = std::max(dp[i], dp[j] * (i - j - 1));
            }
        }
    
        return dp[n];
    }
    
    int main()
    {
        int t, n, item;
    
        cout << "Input n, number of times keys to be pressed: ";
        scanf("%d", &n);
        
        cout << "max no of i's got printed: " << specialKeyboard(n) << endl;
    
        return 0;
    }

**Output:**

**输出：**

Input n, number of times keys to be pressed: 7
    max no of i's got printed: 9

> 翻译自: [https://www.includehelp.com/icp/special-keyboard.aspx][https_www.includehelp.com_icp_special-keyboard.aspx]

键盘特殊

[https_www.includehelp.com_icp_special-keyboard.aspx]: https://www.includehelp.com/icp/special-keyboard.aspx