【Codeforces 1110D】Jongmah

Codeforces 1110 D

题意:给\(n\)个麻将,每个麻将上有一个\(1..m\)的整数\(a_i\)。

现在要将这些麻将们分成一个一个三元组,有两种情况:

  • \([i-1,i,i+1]\)
  • \([i,i,i]\)

然后问最多能将这些麻将们分成多少个三元组。

思路1:

结论:对于每一个三元组\([i-1,i,i+1]\),其出现的次数不会超过两次

证明:

我们如果有\(3\)个\([i-1,i,i+1]\)这种三元组,那么我们可以将其转化成\([i,i,i]\)、\([i-1,i-1,i-1]\)、\([i+1,i+1,i+1]\)这\(3\)个三元组,得到同样的效果。

那么就可以考虑\(dp\)了。

考虑\(dp(i,j,k)\)表示当前已经到了第\(i+1\)个位,\([i-1,i,i+1]\)出现了\(j\)次,\([i-2,i-1,i]\)出现了\(k\)次,最多可以形成的三元组个数。至于状态为什么是这样呢,就是想我们的\(i\)麻将被分到了哪些三元组中,其中和前\(i+1\)个有关的就是这两个。

然后转移的话枚举\([i,i+1,i+2]\)这个三元组出现的次数\(l\),然后\(i\)麻将剩下可以供\([i,i,i]\)的三元组使用的数量就是\(cnt_i-j-k-l\),将\(dp(i+1,k,l)\)赋成\(dp(i,j,k)\)加上这个值\(/3\)再加上\(l\)就行了。

思路2:

我们不考虑\([i-1,i,i+1]\)出现了多少次,我们只考虑被\([i,i,i]\)的三元组用过了之后的\(i\)麻将还剩下多少个。事实证明这个不会超过\(9\)个。为什么呢?首先我们的\(i\)被\([i-2,i-1,i]\)用了最多两次,\([i-1,i,i+1]\)用了最多两次,又被\([i,i+1,i+2]\)用了最多两次,再剩下\([i,i,i]\)一次的余量。

然后也是考虑\(dp\)。\(dp(i,j,k)\)表示当前到了第\(i\)个麻将,\(i-1\)还剩下了\(j\)个,\(i-2\)还剩下\(k\)个。然后转移的时候枚举现在对于\([i-2,i-1,i]\)这个三元组用\(l\)个,肯定是小于等于\(j\)和\(k\)的,那么再看\(cnt_i\)用了\(l\)个后还剩下多少,剩下的如果全用\([i,i,i]\)还剩下多少,记这个值为\(x\),再看如果少用几个\([i,i,i]\)变成了多少,是\(x+3y\)个,其中\(x+3y\)应该小于等于\(cnt_i\)和\(9\)。

然后转移到\(dp(i+1,k,x+3y)\)就好辣。

上一篇:Node.js 常用 API


下一篇:如何添加设备UDID到开发者中心