T
h
e
S
p
o
r
t
s
F
e
s
t
i
v
a
l
The Sports Festival
TheSportsFestival（× ）
链接点我
思考过程
题意：给数字重新排序，
i
i
i从1到
n
n
n，每次用前
i
i
i个数的最大值-最小值，最后把
n
n
n个结果相加，求最小结果
n
n
n的范围可以
n
2
n^2
n2做
f
[
i
]
f[i]
f[i]表示处理到
i
i
i的最大值，
g
[
i
]
g[i]
g[i]表示最小值
顺序随机，所以可以
s
o
r
t
sort
sort?这样值相同的挨得就近了
但是sort之后答案固定，就没法dp了
当选了一个数之后，接下来放的数一定是与它相同的
状态应该不太对，
f
[
i
]
f[i]
f[i]表示选择了
i
i
i个数的答案
……#&……￥@*@……
正解
竟然是一个区间dp，（虽然不是n^3）
首先是基于一定贪心思路的，当sort过之后，答案并没有固定，但是能发现，每次取差距最小，那么取的每个数和之前的数一定都是想连的，就看取左边还是右边了
差距
- 想到贪心，但是没有找到性质
- 误以为区间dp就是n^3
- n^2的dp，状态可以往二维去考虑
B
a
b
a
e
i
a
n
d
B
i
r
t
h
d
a
y
C
a
k
e
Babaei and Birthday Cake
BabaeiandBirthdayCake（×）
链接点我
思考过程
先把体积计算出来
放到桌面上相当于新分了一个组，而每组元素都是单调递增的
lis??
n范围很大，所以要二分；
但是只最长没用，体积不一定最大
二分的指针停留在最后一个元素上，貌似有错。。。
找一个和最大的序列，只有当下一个数大于上一个才能转移
正解
用到了树状数组优化，解决了我解决不了的问题
正常的转移是n^2的，时间复杂度过大，但是用了树状数组之后不用考虑编号了，因为可以直接logn的找到它前面的编号的点，统计答案的话也很方便，改造一下树状数组即可。
同时体积应该按照从小到大的顺序排列，如果相同，就把编号按照从大到小的顺序排列，因为每次只找比自己编号小的，所以先把大的编号加进去，就能保证体积相同的不会被计算，因为如果先加入大的，那么在他开始处理的时候就不会枚举到编号比他小且体积相同的了
差距
- 一直在想普通的dp，没有想到能用数据结构
- 其实这个有一些贪心的思想在，没往这方面考虑
- 没有简化条件，限制条件太多
P
a
w
n
Pawn
Pawn（√）
链接点我
思考过程
n,m<=100，可以n^3?
如果范围小的话可以直接n*2^n暴力dfs
上面一行的状态从下面一行的状态转移，最下面一行应该能赋初值
找方案的话单独算完最大豌豆再去统计
还要满足一个倍数的限制，枚举几倍？
先把最基础的求最大值的dp写出来，没问题
貌似可以写一个类似于背包的转移，f[i][j]表示第i列，所得到的豌豆数量为j,的情况是否可行，这样应该能处理倍数的情况（类似之前的有一道硬币的题？）
这样转移会有问题，i貌似省不掉，1e7的数组？！
第一步完成
总结
正解和我想的一模一样，就是在输出方案的时候有差别，其他没什么
（其实看了一下数据，因为不知道0个也能平均分，写错了）
- 如果遇到凑出数字的题目可以用背包来写，这也算是个模板吧
- 如果用二维状态无法转移，那么就加一维（前提是不爆）
- 看数据范围，心中要有算法的样子
T
o
w
e
r
o
f
H
a
n
o
i
Tower of Hanoi
TowerofHanoi（×）
链接点我
思考过程
熟悉的圆盘问题，记得当时使用dfs写的吧，但是我有点记不清怎么做的了
我决定了，找之前代码看一看！（应该不算看题解吧）
看懂了，但是这个方法有唯一性，肯定不能这样写，但是好像大体思路不变，有可能从1到2再到3比从1到3优
预处理最小值？
写完样例过不去，有可能处理了最小值之后，顺序一遍，放的就不合法了
正解
经典的汉诺塔dfs，但是用两种方法，然后取min，加了一个记忆化搜索，速度起飞
差距
- 对汉诺塔问题不熟练，不知道如何转移圆盘
T
h
r
e
e
C
o
i
n
s
Three Coins
ThreeCoins（）
链接点我
思考过程
n<=500，
n
2
n^2
n2没问题,
n
3
n^3
n3有点悬
是否有某一种情况，使得最后剩下任意一种硬币摆放方式都合法
尽量多的放到正数上
这种区间连续的操作，貌似是区间dp？
没有任何思路啊o(╥﹏╥)o
|