2022-02-23 swipe questions and punch in every day

All in one -- dynamic programming

1274: [example 9.18] merge stones

[Title Description]

N piles of stones are placed in rows on a playground. Now we need to merge the stones into a pile in order. It is stipulated that only two adjacent piles of stones can be selected each time to combine into a new pile, and the number of new piles of stones shall be recorded as the score of the combination.

Calculate the minimum score of combining n piles of stones into one pile.

[input]

The first line is a positive integer N (2 ≤ n ≤ 100);

In the following N lines, each line is a positive integer, less than 10000, representing the number of stones in the ith rockfill (1 ≤ i ≤ N).

[output]

A positive integer, that is, the minimum score.

[input example]

7 
13 7 8 16 21 4 18
[Output example]
239

Let the state f[i] [j] be: from the ith stone to the jth stone, the minimum cost of merging.

We want to merge two piles of stones to minimize the cost. Naturally, the stones on both sides should be as small as possible. Here we use the idea of partition and rule. For example, we want to merge five stones 1,2,3,4,5. We go directly to the last step. The possible result is to take 2 as the dividing point, 1 and 2,3,4,5 as the dividing point, or 3 as the dividing point, Merge 1, 2, 3, 4, 5... We just enumerate the dividing points to see which point is the dividing point. When we find the dividing point, for example, if the dividing point here is 4 and 1, 2, 3, 4 and 5 are merged, then we are repeating the operation of 1, 2, 3, 4 (5 has only one stone, so we don't need it), so we can get the smallest result in the past. Why is the prefix and used when writing here? This is actually optimization. We know that when the last two piles of stones are merged, no matter what happened before, the cost of the last step of merging must be the sum of all stones at the beginning, such as 1 3 5 2 in the example. The cost of the last step is 1 + 3 + 5 + 2 = 11. When enumerating the dividing points, we need to calculate the cost of merging stones after separation. After division and governance, we will finally make there is only one stone on the left and right sides. For example, the merging of 1 and 3 at the beginning of the example is the sum of the first number to the second number. By analogy... (if you don't understand it, it may be that I'm too vague, or you don't understand the idea of divide and conquer). The final answer is on f[1] [n]: the sum of the first stone to the nth stone.

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<unordered_map>
#include<math.h>
#include<queue>
#include<stack>

const int N = 1010;
int f[N][N], s[N];

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> s[i], s[i] += s[i - 1];
	for (int len = 2; len <= n; len++)
	{
		for (int i = 1; i + len - 1 <= n; i++)
		{
			int j = i + len - 1;
			f[i][j] = 1e9;
			for (int k = i; k < j; k++)
			{
				f[i][j] = min(f[i][j],f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
			}
		}
	}
	cout << f[1][n] << endl;
	
	return 0;
}

1289: interceptor missile

[Title Description]

In order to defend against the missile attack of the enemy country, a certain country has developed a missile interception system. However, this missile interception system has a defect: although its first shell can reach any height, each shell in the future cannot be higher than the height of the previous one. One day, the radar caught the enemy's missile attack. Since the system is still in the trial stage, there is only one system, so it may not be able to intercept all missiles.

Input the altitude of the missiles in turn (the altitude data given by the radar is a positive integer of no more than 30000), and calculate the maximum number of missiles that the system can intercept.

[input]

The first line is an integer n (no more than 15), indicating the number of missiles.

The second line contains N integers, which are the altitude of the missile in turn (the altitude data given by the radar is a positive integer not greater than 30000).

[output]

An integer indicating the maximum number of missiles that can be intercepted.

[input example]

8 
389 207 155 300 299 170 158 65
[Output example]
6

Longest decreasing subsequence

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<string.h>
#include<string>
#include<unordered_map>
#include<math.h>
#include<queue>
#include<stack>

const int N = 1010;
int f[N], h[N];

int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)cin >> h[i];
	f[0] = 1;
	int res = 1;
	for (int i = 1; i < n; i++)
	{
		f[i] = 1;
		for (int j = i - 1; j >= 0; j--)
		{
			if (h[j] > h[i])
			{
				f[i] = max(f[i], f[j] + 1);
				res = max(res, f[i]);
			}
		}
	}
	cout << res << endl;
	return 0;
}

Blue Bridge Cup - algorithm improvement

Algorithm improves P0603

Write a program, input a sentence, and then count the number of different words in the sentence. For example, for the sentence "one little two little three little boys", there are five different words in total, one, little, two, three, boys.

explain

(1) Since the sentence contains spaces, you should use the gets function to enter the sentence.
(2) the input sentence contains only English characters and spaces, and the words are separated by a space.
(3) regardless of the case of words, it is assumed that the input characters are all lowercase characters.
(4) sentence length shall not exceed 100 characters
Input:
　　one little two little three little boys
Output:
　　5

#include<iostream>
using namespace std;
#include<map>
#include<string>

const int N = 100010;
int f[2][N];

int main()
{
	int res = 0;
	string str;
	getline(cin, str);
	int n = str.size();
	string s;
	map<string, int>mymap;
	for (int i = 0; i < n; i++)
	{
		if (str[i] == ' ' && s.size())
		{
			mymap[s]++;
			s.clear();
		}
		else s += str[i];
	}
	if(s.size())
	{
		mymap[s]++;
		s.clear();
	}
	cout << mymap.size() << endl;
		
	return 0;
}