js \n直接顯示字符串
Problem statement:
問題陳述：
You need to display N similar characters on a screen. You are allowed to do three types of operation each time.
您需要在屏幕上顯示N個相似的字符。 每次允許您執行三種類型的操作。
You can insert a character,
您可以插入一個字符，
You can delete the last character
您可以刪除最后一個字符
You can copy and paste all displayed characters. After copy operation count of total written character will become twice.
您可以復制并粘貼所有顯示的字符。 復制操作后，總書寫字符數將變為兩倍。
All the operations are assigned different times.
所有操作均分配有不同的時間。
Time for insertion is X
插入時間為X
Time for deletion is Y
刪除時間為Y
Time for copy, paste is Z
復制時間，粘貼為Z
You need to output minimum time to display N characters on the screen using these operations.
使用這些操作，您需要輸出最短時間以在屏幕上顯示N個字符 。
Input:
輸入：
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer N denoting the number of same characters to write on the screen. The next line contains time for insertion, deletion, and copying respectively.
輸入的第一行包含一個整數T，表示測試用例的數量。 然后是T測試用例。 每個測試用例都包含一個整數N，該整數N表示要在屏幕上寫入的相同字符的數量。 下一行分別包含插入，刪除和復制的時間。
Output:
輸出：
Print the minimum time to display N characters on the screen.
打印最短時間以在屏幕上顯示N個字符。
Constraints:
限制條件：
1 <= T <= 100
1 <= N <= 100
1 <= X, Y, Z <= N
Example:
例：
Input:
Test case: 2
First test case,
N, number of characters to be displayed = 9
Value of X, Y, Z respectively,
1 2 1
N, number of characters to be displayed = 10
Value of X, Y, Z respectively,
2 5 4
Output:
minimum time for first test case: 5
minimum time for second test case: 14
Explanation:
說明：
For the first test case no of character to be displayed is: 9
Time for insertion is 1
Time for deletion is 2
Time for copy paste is 1
Say the similar character is 'a'
So the best way is
Insert two character
Time is 2
Copy paste
Total character so far is 4
Total time 3
Copy paste again
Total character so far is 8
Total time 4
Insert gain
Total character so far is 9
Total time 5
This is the most optimum way we can solve this
Solution Approach:
解決方法：
This is a recursive problem
這是一個遞歸問題
And we have a few possibilities,
我們有幾種可能性，
Simply insert
只需插入
Copy-paste
復制粘貼
Delete
刪除
Now we need to understand the optimal option based on the situation
現在我們需要根據情況了解最佳選擇
Say a situation where we need to reach character 13 and we are at character 7 displayed already
假設有一種情況，我們需要到達第13個字符，并且已經顯示了第7個字符
Also, Cost of Inserting 6 digits is much higher than one-time copy paste and deleting ( just consider this case, it may not happen always if copy paste option is costly)?
另外，插入6位數字的成本比一次性復制粘貼和刪除要高得多(僅考慮這種情況，如果復制粘貼選項成本很高，則可能不會總是發生)
So, the question is when the "delete" options is useful
因此，問題在于何時使用“刪除”選項
It's useful for such case what I mentioned. So if we formulate the recursion
我提到的這種情況對這種情況很有用。 所以如果我們制定遞歸
Say,
說，
N = number of characters to be displayed.
N =要顯示的字符數。
So, if n is odd only then we need deletion if n is we even don't need that.
所以，如果n是奇數只有這樣，我們需要刪除，如果n是我們甚至不需要這樣。
Now, we have our recursion, so we can write the recursive function. Since there will be many overlapping sub-problems, we can wither use top-down DP or bottom-up DP. I have used memoization in my implementation. As an exercise, you should be able to convert the above recursion to tabulation DP.
現在，我們有了遞歸，因此我們可以編寫遞歸函數。 由于將存在許多重疊的子問題，因此我們可以使用自頂向下的DP或自底向上的DP。 我在實現中使用了記憶。 作為練習，您應該能夠將上述遞歸轉換為表格DP。
C++ Implementation:
C ++實現：
#include <bits/stdc++.h>
using namespace std;
int dp[101];
int minimum(int a, int b)
{
return a > b ? b : a;
}
int my(int cur, int x, int y, int z)
{
if (cur == 1) {
return x;
}
// meoization, dont compute what's already computed
if (dp[cur] != -1)
return dp[cur];
if (cur % 2 == 0) { //for even n
dp[cur] = minimum(x + my(cur - 1, x, y, z), z + my(cur / 2, x, y, z));
}
else { //for odd n
dp[cur] = minimum(x + my(cur - 1, x, y, z), z + y + my((cur + 1) / 2, x, y, z));
}
return dp[cur];
}
int main()
{
int t, n, item;
cout << "enter number of testcase\n";
cin >> t;
for (int i = 0; i < t; i++) {
cout << "Enter number of characters\n";
cin >> n;
int x, y, z;
cout << "Insert time for insertion, deletion and copy respectively\n";
cin >> x >> y >> z;
for (int i = 0; i <= n; i++)
dp[i] = -1;
cout << "Minimum time is: " << my(n, x, y, z) << endl;
}
return 0;
}
Output:
輸出：
enter number of testcase
3
Enter number of characters
8
Insert time for insertion, deletion and copy respectively
3 2 5
Minimum time is: 16
Enter number of characters
8
Insert time for insertion, deletion and copy respectively
1 1 3
Minimum time is: 7
Enter number of characters
3
Insert time for insertion, deletion and copy respectively
1 4 6
Minimum time is: 3
翻譯自: https://www.includehelp.com/icp/minimum-time-to-display-n-character.aspx
js \n直接顯示字符串
