Codeforces Round 1110
这场比赛只做了\(A\)、\(B\)、\(C\),排名\(905\),不好。
主要的问题在\(D\)题上,有\(505\)人做出,但我没做出来。
考虑的时候方向不对,一直抠一个思路不放,然后就一直做不出来。
虽然我中间也考虑过其他的思路,但是都没有思考完善,于是就一直在给我原来的方法加补丁。
Codeforces 1110 D
题意:给定一个序列,问最多可以把该序列分成几个满足下列两个条件之一的三元组:
- 这三个数字相同
- 这三个数字为连续的三个数
思路:首先因为三次取连续可以分成三次取相同,所以最多有两次连续。然后考虑\(dp\):\(dp(i,j,k)\)表示到了\(i\)这个数,\(i\)作为连续的三个数的中心取了\(j\)次,\(i+1\)作为连续的三个数的中心取了\(k\)次,可以取的最多的三元组个数。转移方程:
\(dp(i,k,l)=max(dp(i,k,l),dp(i-1,j,k)+l+(a_i-j-k-l)/3)\)
反思:此题我在比赛时想的方法是考虑先取数值相同的三元组,看每个数字取完后还剩下多少(猜了个肯定不超过\(5\)的结论(其实是不超过\(9\)),然后发现得不断地加补丁修正,因为自己也在不断发现比原来认为的范围更大的反例),然后就陷入其中出不来了。