花店橱窗布置

思路

• f[i][j]f[i][j]表示前i个花瓶前j个花束的最大美学价值
• f[i][j]=max(f[i−1][k],f[i][j])f[i][j]=max(f[i−1][k],f[i][j])

当然还有另外一种思路(*太强了！！！*)：

• 整张表都是向右下方走的，向下走加上数值，向右走无影响
• 如果向下走代表花束放入花瓶，向右走无影响代表不放入

1
2
3
4

int f[N][N],mp[N][N];
for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
        f[i][j]=max(f[i-1][j]+mp[i][j],f[i][j-1]);

矩阵取数

思路

• 因为每次取头和尾，所以一定是一个连续的区间
• f[i][j]f[i][j]表示从i取到j的最大得分
• $f[i][j]=max(f[i][j-1]+a[j]*2^(i-1+n-j+1+1) \ , \ f[i-1][j]+a[i]*2^(i-1+n-j+1+1))$
• 指数是轮数，当前数前面有多少个数被取走，就有多少轮，注意一下1的问题

传纸条

思路

• f[i][j][k][l]f[i][j][k][l]表示现在去的到了(i,j),回来的到了(k,l)

• 一共有四种情况，上上，左左，上左，左上

• 保证两条路径不相交if(j1==j2 && i1==i2) continue

• f[i][j][k][l]=max(f[i−1][j][k−1])f[i][j][k][l]=max(f[i−1][j][k−1])

• 步数为i+j−1i+j−1

• 判断不合法的状态

  1 2	if(i1+j1!=i2+j2) continue; if(i1==i2 && j1==j2 && i1+j1!=2 && i1+j1!=m+n) f[i1][j1][i2][j2]=-0x3f3f3f3f;

• 当m,n<100m,n<100时，四维数组开不下了，因为i1+j1=i2+j2i1+j1=i2+j2的时候才是合法的，并且三个数都确定时，我们可以直接算出j2j2,直接变成了三维

免费馅饼

题目

地面长度为L，高度为H，天上掉馅饼

人在地上每单位时间可以向左或向右移动0~2格，馅饼每单位时间掉落一格

求最多接到多少馅饼（馅饼有分值）

思路

• f[i][j]f[i][j]表示第i秒到达第j个格子的最大得分
• 该状态是从哪里转移过来的呢？ 他可以从5个地方转移过来（没有到边界的时候）
• 运动具有相对性，我们可以把该问题类比成数字三角形，相当于馅饼不动，人每次向上移动一个单位
• f[i][j]=ff[i][j]=f

三角蛋糕

思路

• 像数字三角形一样压缩成正三角形
• f[i][j]=min(f[i+1][j],f[i+1][j+1])+1f[i][j]=min(f[i+1][j],f[i+1][j+1])+1

金明的预算方案

思路：分组背包

• f[i][j]f[i][j]表示前i组物品重量不超过j的最大价值
• 一共5种转移方式
• f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5f[i][j]=max(f[i−1][j],f[i−1][j−w[i][k]]+v[i][k]),k=1,2,3,4,5,五种情况已经重新配置的前提下

01/完全背包混合

• 根据物品的类型选择状态转移方程

二维限制的背包

• 把数组扩展成三维
• f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])f[i][j][k]=max(f[i−1][j][k],f[i−1][j−w[i]][k−v[i]]+c[i])

面包

题目

有N种面包，每种面包数量无限多，有高度和价值，高度是5的倍数
将面包叠成一个面包塔，高度不得超过T
给定常数k，若一个面包高度>=k，则它下面所有面包都会被压扁
一个面包最多被压扁一次，它的高度变为原来的4/5
求最大的价值

思路

• 如果没有面包被压扁，就是一个完全背包问题
• 如果有大面包，肯定要放到最上面，使得压缩高度尽可能大
• 枚举最上面是哪一个大面包，然后其余所有面包的高度都变为原来的五分之四，就转化成了一半的完全背包问题

二叉苹果树

思路

• $dp[u][j表示节点u留下j条边的最大价值，每一次决策只有三种情况：剪左子树，剪右子树，两个都不剪
• 剪左边：dp[u][j]=dp[rson][j−1]+v[rson]dp[u][j]=dp[rson][j−1]+v[rson]，同理，剪右边：dp[u][j]=dp[lson][j−1]+v[lson]dp[u][j]=dp[lson][j−1]+v[lson]
• 两边都不剪：dp[u][j]=dp[lson][j]+dp[rson][k−j−2]dp[u][j]=dp[lson][j]+dp[rson][k−j−2]

代码：记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int f[N][N];
bool t[N][N];
int dp(int u,int k)
{
    if(t[u][k]) return f[u][k];
	t[u][k]=1;
    if(!k) return f[u][k]=0;
    int tmp1=dp(lson[u],k-1)+v[sonl[u]];
    int tmp2=dp(rson[u],k-1)+v[sonr[u]];
    int tmp3=0;
    for(int l=0;l<k-2;l++)
        tmp3=max(tmp3,dp(lson[u],l)+dp(rson[u],k-l-2));
   	return f[u][k]=max(tmp1,max(tmp2,tmp3+lson[u]+rson[u]));
}

先修课

题目

课的先修关系形成一棵树的结构，每门课有一门或者没有先修课。选M门课，能获得的最大学分是多少？

思路

• dp[u][j]dp[u][j]以u为根的子树选j门课
• 把j-1门课分配给子树，就是一个背包？
• 然后我们用f[i][j]f[i][j]表示当前树中，前i棵子树选择j门课的最大学分。这样就能够通过f算出dp[i][j]dp[i][j],相当于树上DP套背包。对于每一个状态dp[i][j]dp[i][j]都需要用f算出学分分配的最佳方案

K-set

题目

在一棵树中选出最多的点，使得这些点中每个点最多与其他点连了k条边

思路

• dp[u][0/1][0/1]dp[u][0/1][0/1]表示以u为父亲，取/不取父亲,取/不取自己的最大值

• dp[u][0][0]dp[u][0][0]：自己和父亲都不取，u的儿子随便取。$f[u][0][0]=size∑i=1max( dp(vi,0,0) , dp(vi,0,1) )f[u][0][0]=∑i=1sizemax( dp(vi,0,0) , dp(vi,0,1) )$

• dp[u][1][0]dp[u][1][0]：父亲要取，u自己不取，u的儿子同样随便取。f[u][1][0]=f[u][0][0]f[u][1][0]=f[u][0][0]

• dp[u][1][1]dp[u][1][1]

  ：父亲要取，自己也要取，儿子取k-1条边。

  • 这时我们就要考虑取哪几条边，也就是哪几个点。
  • 对于任意一个u的儿子vivi,如果取这个点，那么它的贡献就是dp(vi,1,1)dp(vi,1,1)，如果不取这个点，那么它的贡献就是dp(vi,1,0)dp(vi,1,0)
  • 因此这个点取或者不取，带来的贡献就是两种情况的差，所以我们只要按两种情况的差从大到小排序就好了。最后选取差值最大的k-1个点就OK了（前提是这k-1个点带来的贡献都是正的，如果有负贡献那么就取不满k-1个点）

• dp[u][0][1]dp[u][0][1]：父亲不取，自己要取，儿子取k条边

The server’s previous technical issues have caused the loss of images and data.

济南Day1 随记

终于，还是决定出去闯一闯。

不知为何，我似乎是厌倦了学校的生活，每一次上下课的铃声似乎在震颤着我的内心。

希望能有所收获。

第一次知道飞机票打起折来居然比高铁票还便宜。

然后买了早上十一点的飞机票。

很早就起来了，老爸把我送上机场大巴，我却没想到他买了两张车票。

到了机场，通过自助值机拿到了登机牌，跟老爸打完招呼就进去安检了。机场里人也很少，很安静，就像细水流淌一样，心间也少了一份激动，更多的是均匀的呼吸，平和的心跳。

上了飞机，好像是空客A320。我坐在第37排，莫名感到非常拥挤。想试着调节一下座椅，却无奈找不到调节开关。比较尴尬地询问了空姐，才得知紧急通道的前面一排是没有座椅调节功能的……（温馨提示千万不要选紧急通道附近的座位）。也不知道是不是心理作用，反正整个航班都坐的很不舒服。旁边坐着一位大学生姐姐，知道快下降了我们才说话，她十分同情高一悲催成狗的我……

下了飞机，等大巴。我和大连的一行人一块走，他们的航班3点多才抵达，我就坐在国内到达的椅子上死等。整个济南遥墙机场特别小，就一个航站楼，说实话觉得还没有西安北客站大（当然不不包括飞机滑行面积）最后找大巴还找了很久……突然发现了一个叫做贵宾楼的东西，整个航站楼一半都是贵宾楼……

到了酒店，我一个人一个房间。在房间里睡了会儿觉，看了一下DP就去吃饭了。

就这样，期待新的一天。

The server’s previous technical issues have caused the loss of images and data.

济南Day2 随记

今天是第二天，收获颇丰。

也不知道什么时候我定了一个6：00的闹钟，基本上响了之后就没怎么睡觉了。早上6：50起床，洗漱之后穿好衣服就去餐厅吃饭。这个酒店的楼梯很玄学，我的房间旁边的小楼梯直达上课的会议室和餐厅后门，感觉像是Minecraft一样，很小的楼梯。

早上的饭还说的过去，就是没有勺子，喝粥的时候撒了一手。

然后去教室，我的位置特别好。第一排而且正对着老师。

周围的同学特别活跃，搞得我也愿意跟老师交流，把自己不成熟的想法说出来。还说对了好多，突然有一种莫名的喜悦感。早上的课干货满满，感觉受益匪浅。很多问题也都是自己思考出来的。

中午我见到了我的室友，他才初二，上基础班。和他很投的来，也有很多共同话题。他也特别喜欢科技方面的东西，我们聊了挺久的。

中午睡了大概一个小时然后我们就各奔各自教室了。下午我们讲的是DP，各种DP，虽然不是很难，但是脑子快炸了。但第一次听如此繁杂的东西听得如此开心。

晚上和室友去了KFC，真的好贵而且没吃饱，但无奈不想吃外卖（好像没什么区别），而且周围也没什么好吃的，只能将就一下了……

感觉济南真的没有一个省会城市的风度，人特别多，感觉街上特别乱。当然，只是我的主观臆断。

晚上是答疑和刷题。我就只做了三道题，但是感悟颇深。至少都是自己做出来的。

今天的笔记还没有写完，就说到这，晚安！

期末考试……

该来的终究还是来了，欠下的终究是要还的

同时祝大佬们冬令营集训顺利！

基本公式：

要取得[a,b)的随机整数，使用(rand() % (b-a))+ a;
要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a;
要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1;
通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。
要取得a到b之间的随机整数，另一种表示：a + (int)b * rand() / (RAND_MAX + 1)。
要取得0～1之间的浮点数，可以使用rand() / double(RAND_MAX)。

这是我到目前为止写过最长的代码之一……

题意

4*4的棋盘，一共有三种属性：白棋，黑棋，空格（有且仅有两个），每一次可以移动一颗棋子，黑白棋交替进行，只能移到空格的地方。求达成四子连棋局面（横竖斜都算）所需的最小步数

分析

• 广搜，和八数码问题差不多，但是更繁琐了。
• 黑白棋交替进行，那么我们需要在搜索的时候除了当前地图和步数还需要保存当前该哪一方行棋
• 广搜要搜两遍，分别是黑棋先走或白棋先走
• 每一次需要考虑两个空格，所以从两个当前点搜状态

遇到的坑

• 很多都是重复的代码，只要细心就好了，但有一个*最坑的……*

• 黑棋先走和白棋先走走到的棋局相同的情况也是两种情况，不能判重删去！！！

STL

C++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让用户在STL使用过程中，并不会感到陌生。

迭代器

1
2

set<int>::iterator it_set//一个set<int>类型的迭代器
map<string,int>::iterator it_map//一个map<string,int>类型的迭代器

SET

set的各成员函数列表

1. begin()–返回指向第一个元素的迭代器
2. clear()–清除所有元素
3. count()–返回某个值元素的个数
4. empty()–如果集合为空，返回true
5. end()–返回指向最后一个元素的迭代器
6. equal_range()–返回集合中与给定值相等的上下限的两个迭代器
7. erase()–删除集合中的元素
8. find()–返回一个指向被查找到元素的迭代器
9. get_allocator()–返回集合的分配器
10. insert()–在集合中插入元素
11. lower_bound()–返回指向大于（或等于）某值的第一个元素的迭代器
12. key_comp()–返回一个用于元素间值比较的函数
13. max_size()–返回集合能容纳的元素的最大限值
14. rbegin()–返回指向集合中最后一个元素的反向迭代器
15. rend()–返回指向集合中第一个元素的反向迭代器
16. size()–集合中元素的数目
17. swap()–交换两个集合变量
18. upper_bound()–返回大于某个值元素的迭代器
19. value_comp()–返回一个用于比较元素间的值的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;
set<int> s;
set<int>::iterator it_set;

int main()
{
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int tmp;
		scanf("%d",&tmp);
		s.insert(tmp);
	}
	for(it_set=s.begin();it_set!=s.end();it_set++)
	{
		printf("%d\n",*it_set);
	}
	return 0;
}

链接

容器set和multiset

P1284三角形牧场

题意

现在有n段木棍，全部使用组成三角形的三条边，使三角形的面积最大

分析

• 首先看数据范围，边长最大为40*40/3，并且因为要使用所有的木棍，所以只要两条边确定就可以知道第三条边的确定长度。因此我们可以设状态f[i][j]表示三角形的两条边分别是i，j的情况是否成立

• f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]f[i][j]=f[i−a[k]][j] || f[i][j−a[k]] || f[i][j]，相当于01背包，就不解释了……

• 定义初始状态f[0][0]=1f[0][0]=1

• 三条边都知道了，如何求面积呢？这里我们需要用到海伦公式

  S=√p(p−a)(p−b)(p−c)S=p(p−a)(p−b)(p−c)，p=12(a+b+c)p=12(a+b+c)

遇到的坑

好像没有什么

P1929 迷之阶梯

真的好坑，做了一下午……

题意

登上阶梯必须要按照它要求的方法， 否则就无法登上阶梯。它要求的方法有以下三个限制：

1. 如果下一步阶梯的高度只比当前阶梯高 1，则可以直接登上。
2. 除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。
3. 当你连续退下 k 后，你可以一次跳上不超过当前阶梯高度 2^{k}2k的阶梯。比如说你现 在位于第 j 步阶梯，并且是从第 j+k 步阶梯退下来的，那么你可以跳到高度不超过当前阶 梯高度+2^{k}2k的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯，由于时间紧迫，我们需要用最少的移动次数登上迷之阶梯。 请你计算出最少的移动步数。

分析

• 定义状态为f[i]表示到第i个阶梯的最小步数
• 由2可以直接得出if(h[i]==h[i-1]+1) f[i]=f[i-1]+1

遇到的坑

• if(f[n]>=0x3f3f3f3f) f[n]=-1;在状态转移的过程中有可能比初始值更大，所以是大于等于