2022-02-23每日刷题打卡

一本通——动态规划

1274：【例9.18】合并石子

【题目描述】

在一个操场上一排地摆放着Ｎ堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的２堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

计算出将Ｎ堆石子合并成一堆的最小得分。

【输入】

第一行为一个正整数N (2≤Ｎ≤100)；

以下Ｎ行,每行一个正整数，小于10000，分别表示第i堆石子的个数(1≤i≤N)。

【输出】

一个正整数，即最小得分。

【输入样例】

7 
13 7 8 16 21 4 18
【输出样例】
239

设状态f[i] [j]为：从第i个石头到第j个石头，合并所需的最少代价。

我们想和并两堆石头，使其代价最少，那自然是要两边的石头都尽可能的小了，这里用的是分治的想法，比如我们想把5块石头1,2,3,4,5合并，我们直接到最后一步来，可能的结果是以2为分界点，1和2 3 4 5合并，也可以是以3为分界点，1 2和3 4 5合并……我们就这样枚举分界点，看以哪个点为分界点时，两边的值都尽可能的小，当我们找到了分界点后，比如假设这里的分界点是4，是1 2 3 4和5合并，那么我们我们在对1 2 3 4做重复操作（5只有一个石头就不需要了），由此以往得到最小的结果。为什么这里写的时候用到了前缀和，这其实是优化，我们知道，当最后两堆石头合并时，不管先前咋样，这最后一步的合并所需代价必然是所有石头一开始的总和，比如样例的1 3 5 2，最后一步所需代价就是1+3+5+2=11。我们在枚举分界点的时候，要计算分开后，合并石头的代价，我们经过分治，最后会使得左右两边只有一个石头，比如样例一开始的1 3合并，那么就是第一个数到第2个数的总和。以此类推……（如果没太搞懂也可能是我讲的太模糊，也可能是你不懂分治的思路），最后答案就在f[1] [n]上：第1个石头到第n个石头的总和。

#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：拦截导弹

【题目描述】

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)，计算这套系统最多能拦截多少导弹。

【输入】

第一行是一个整数N(不超过15)，表示导弹数。

第二行包含N个整数，为导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数)。

【输出】

一个整数，表示最多能拦截的导弹数。

【输入样例】

8 
389 207 155 300 299 170 158 65
【输出样例】
6

最长递减子序列

#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;
}

蓝桥杯——算法提高

算法提高 P0603

编写一个程序，输入一个句子，然后统计出这个句子当中不同的单词个数。例如，对于句子“one little two little three little boys”，总共有5个不同的单词，one, little, two, three, boys。

说明

（1）由于句子当中包含有空格，所以应该用gets函数来输入这个句子。
　　（2）输入的句子当中只包含英文字符和空格，单词之间用一个空格隔开。
　　（3）不用考虑单词的大小写，假设输入的都是小写字符。
　　（4）句子长度不超过100个字符
输入:
　　one little two little three little boys
输出:
　　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;
}