近期题目来自校赛,赛前训练,省赛热身,河北ccpc正式比赛。

河北ccpc告一段落,但是算法之路刚刚开始,自己会的东西其实很少,有大量的知识需要学,

本篇主要写dp,写简单的,主要起到启发和提高思维的作用了,套路题一律不写。

 

校赛:

题目一:

题目描述:

由于第m个台阶上有好吃的薯条,所以薯片现在要爬一段m阶的楼梯.
薯片每步最多能爬k个阶梯,但是每到了第i个台阶,薯片身上的糖果都会掉落ai个,现在问你薯片至少得掉多少糖果才能得到薯条?

输入:


多组数据输入,每组数据第一行输入两个数字m(1<m<=1000),k(1<=k<m),接下来有m行,每一行输入ai(0<ai<=1000),表示第i个台阶会掉落的糖果.

输出:

对于每组数据,输出至少要牺牲的糖果数.

样例输入

5 2
1 2 3 4 5
6 2
6 5 4 3 2 1

样例输出

9
9

分析:经过的数字全部加起来,为一个累加和,求最小累加和

递推关系:

定义f(n)为必须到第n个台阶的最少累加和

分析可以如何得到f(n),我们通过跳一步,可以怎么跳到第n个台阶呢?

可以从第n-1个台阶跳到这里,可以n-2,n-3......n-k。

也就是说,

f(n)=an+min(f(n-1),f(n-2),......f(n-k))

必须到第n个台阶的最少累加和,就等于能跳到这里的所有位置中,最小的那个f(),跳过来(也就是加上本身)。

注意:前k个台阶可以从起点直接跳过来,贪心思想,经过任何多余的数字都不会是最优解。所以前k个f(n)直接赋值an.

也可以维持单调队列把时间降到线性,不过o(n*k)已经足够过了。

本题结束

 

题目二:

题目描述:

JiangYu的小金库是一个三维立体的空间,大小为XYZ,里面每个位置都藏着各种价值的宝物,既然是宝物价值自然非同一般,可正可负。

可恶的花花得知了这一切,想要偷走其中的珍宝们。

可是Jiangyu的小金库安保措施十分严密,花花只有一次行动的机会,他决定偷走一个价值尽可能大的长方体区间。

那么他最大能偷走多少钱的宝物呢?

输入:

第一行给出三个正整数 X,Y,Z

第二行一个整数n, 宝藏的数量

接下来n行,每行给出一个宝藏的位置xi,yi,zi, 以及价值ci

保证宝藏位置不重复。 (1 \leq X,Y,Z \leq 201≤X,Y,Z≤20)

(1 \leq n \leq X \times Y \times Z1≤n≤X×Y×Z)

(1 \leq xi \leq X1≤xi≤X)

(1 \leq yi \leq Y1≤yi≤Y)

(1 \leq zi \leq Z1≤zi≤Z)

(-1e9 \leq ci \leq 1e9−1e9≤ci≤1e9)

输出:

一个整数,最大的价值

样例输入

2 2 2
8
1 1 1 10
1 1 2 9
1 2 1 10
1 2 2 9
2 1 1 10
2 1 2 9
2 2 1 -1
2 2 2 10

样例输出

66

 

https://blog.csdn.net/hebtu666/article/details/82788866
<https://blog.csdn.net/hebtu666/article/details/82788866>这个网址写了详细讲解哦。。。最好要看看

首先要明白一维最大子数组问题,设dp[n]的含义为必须以an结尾的数组中的最大和。

所以dp[n]就是,每一个以在n前面的结尾的最大值,加上an.

二维方法:转化为一维来做。枚举长度为原矩阵长度的所有矩阵。然后压成一维来做。

时间:

因为有n个开头,每个开头有n-1,n-2......1个结尾,所以枚举的时间复杂度为o(n^2)。

为了节省时间,利用预处理数组思想,定义长宽和原矩阵一样的矩阵gg。


每列满足第n列k行的值为sum(l[0][n]+l[1][n]....l[k][n]),可以o(n*m)做到(nm为长宽).然后枚举到某矩阵的时候直接根据gg得出。整体做到o(n^2)枚举并求和。然后按一维做。整体o(n^3)

三维:并没有什么高大上的优化,也是枚举每一个长宽固定的长方体,压缩至二维,然后按二维做。

本题结束

 

题目三:

热身赛,并没有原题,手打。

过的队伍不多

一种动物,出生到死亡只有三年,即n年出生,n+3年死去。

出生一年以后可以生育,也就是n+1年开始生育,一年可以生一只宝宝。

定义第n年动物总数为an,给定n,返回an/a(n-1),最多保存小数点后十位

第一年有一只

思路一:定义f(n)为第n年新出生的动物个数,则f(n)=f(n-1)+f(n-2),前两项为1,而每年的总数也就是三项求和而已。

每年出生的数量为1,1,2,3,5,8,13,21

每年总数就是1,2,4,10,16,26,42

发现是斐波那契数列

思路二:直接从总数入手,定义f(n)为第n年的总数


如何求出an/a(n-1):要看有多少动物能活到n年,活不到n年的也不能在第n年生育,活到n年的动物每人生一个,所以an就是二倍的能活到n年的动物。求此数方法很多,在此只说一个:

f(n-1)-(1/2)f(n-3)

去年的数量减去,去年还活着的今年就死了的数量。


这个数乘二,得出答案f(n)=2f(n-1)-f(n-3),其实本质还是斐波那契,因为f(n-1)=f(n-2)+f(n-3),带入以后发现f(n)=f(n-1)+f(n-2)。

式子写出来了,但是原题数据范围是10^1000,不能一项一项推过去。

尝试发现,几十项之后,an/a(n-1)的十位小数之内都没有变过,所以当数字较大时直接输出第五十项即可。

本题结束

但是还有点别的东西想写

 

斐波那契的美

万物之美,总能找到斐波那契数列的规律。随着n的增加,an/a(n-1)越来越接近黄金分割

手写了求解过程。可能写的不规范,但是就是表达这个意思。

 

只要数列满足X(n) = X(n-1) + X(n-2),无论前两个值是多少,都满足黄金分割的条件,而斐波那契数列是最简单的特例:前两个元素均为1

数学家还发现了费马大定理和这个数列的关系(费马大定理的证明,三百五十年),并应用到诸多领域(比如加密)。有兴趣自行了解。

 

题目四:

省赛,没有原题。十六支队伍过了这个题。

https://blog.csdn.net/hebtu666/article/details/79964233
<https://blog.csdn.net/hebtu666/article/details/79964233>

参考我前面的文章,dp入门篇,那个会了这个就会。

参考萌新题

现场因为对c++不熟,没敢压空间,规规矩矩的写了一遍,还因为多打了一行罚了时,跟智障一样。。。

 

 

题目五

http://newoj.acmclub.cn/contests/1359/problem/6
<http://newoj.acmclub.cn/contests/1359/problem/6>

题意:最长公共子序列,要求序列每个元素重复k次,比如1122重复两次,111222重复三次。

输入两个字符串和k,输出长度。

最长公共子序列的一个变形。。。

动态规划。设dp[i][j]表示a串处理到i位置,b串处理到j位置的答案。预处理出从a串i位置向前数,第k个与i位置数
字相同的位置p[i],用相同方式处理出B串的q[i]。

则转移方程为dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-p[i]][j-q[j]]+1),其中第三种转移必须在a[i]=b[j]的情况下转移。

 

代码都是比赛时候写的,真的不想找来贴了。

 

最后总结经验教训:

 

注意细节,注意细节,注意细节

多种思路,多种思路,多种思路

递归关系自己推,比如背包,你要是看套路。。。Emmm。。就连套路都不会用了。

平时递归关系自己推,自己推,自己推。