【Codeforces Round 1110】Codeforces Global Round 1

时间:2024-08-10 09:06:38
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\)),然后发现得不断地加补丁修正,因为自己也在不断发现比原来认为的范围更大的反例),然后就陷入其中出不来了。