P5019 铺设道路 && P1969 积木大赛 && P3078 扑克牌型

题目描述

春春是一名道路工程师,负责铺设一条长度为n的道路。
铺设道路的主要工作是填平下陷的地表。整段道路可以看作是n块首尾相连的区域,一开始,第i块区域下陷的深度为di。
春春每天可以选择一段连续区间[L,R],填充这段区间中的每块区域,让其下陷深度减少1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为0。
春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为0。

输入输出格式

输入格式:

输入文件包含两行,第一行包含一个整数n,表示道路的长度。第二行包含n个整数,相邻两数间用一个空格隔开,第i个整数为di。

输出格式:

输出文件仅包含一个整数,即最少需要多少天才能完成任务。

输入输出样例

输入样例#1:

1
2
6   
4 3 2 5 3 5

输出样例#1:

1
9

说明

【样例解释】
一种可行的最佳方案是,依次选择:[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4、[6,6]、[6,6]。
【数据规模与约定】
对于30%的数据,1≤n≤10;对于70%的数据,1≤n≤1000;对于100%的数据,1≤n≤100000,0≤di≤10000。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;

int n,num[1000000];
long long ans;

int main(void)
{
cin >> n;
for(int i = 1;i <= n;++i)
cin >> num[i];
for(int i = 1;i <= n;++i)
if(num[i] > num[i-1])
ans += num[i] - num[i-1];
cout << ans;
return 0;
}

P5020 货币系统

题目描述

在网友的国度中共有 n种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作 (n,a)。

Read More

其实真正懂纯音乐、欣赏纯音乐、喜欢听纯音乐的人,很多都是有抑郁症或自卑或真正孤独的人。他们喜欢在纯音乐中独自品味这常人根本无法忍受的孤独,他们喜欢在喜欢的纯音乐中回忆过去种种的美好。不喧哗、不世故、不擅长交际、和善待人、有自己的想法和信念。愿爱听纯音乐的我们会被这个世界温柔相待♥

博客无限期停更! ——2019-04-16 09:12:40

题解 P1093 奖学金

题目描述

某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学 排在前面,这样,每个学生的排序是唯一确定的。

Read More

题解P1002 过河卒

题目描述

棋盘上A点有一个过河卒,需要走到目标B点。卒行走的规则:可以向下、或者向右。同时在模盘上C点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示,A点(0,0)、B点(n,m)(n,m为不超过20的整数),同样马的位置坐标是需要给出的。
现在要求你计算出卒从A点能够到达B点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。

输入输出格式

输入格式:

一行四个数据,分别表示B点坐标和马的坐标。

输出格式:

一个数据,表示所有的路径条数。

输入输出样例

###输入样例#1:

1
6 6 3 3

输出样例#1:

1
6

说明

结果可能很大!

题解

这涉及到高中所学的加法原理。

然后易得DP转移方程:$dp[i][j] = dp[i-1][j] + dp[i][j-1]$ 前提是马够不到的距离下是这样。

题解P1308 统计单词数

题目描述

一般的文本编辑器都有查找单词的功能,该功能可以快速定位特定单词在文章中的位置,有的还能统计出特定单词在文章中出现的次数。

现在,请你编程实现这一功能,具体要求是:给定一个单词,请你输出它在给定的文章中出现的次数和第一次出现的位置。注意:匹配单词时,不区分大小写,但要求完全匹配,即给定单词必须与文章

中的某一独立单词在不区分大小写的情况下完全相同(参见样例1 ),如果给定单词仅是文章中某一单词的一部分则不算匹配(参见样例2 )。

Read More