题意:给\(n\)个队伍的积分,它们要踢足球,每个队伍剩下4场没有踢。
问踢完后\(0\)队伍最高排名。
思路:首先想了贪心,可惜不对。
那么老实dp。
首先:每个队伍具体和哪个人踢了没有关系。
那么我们只关心一个队伍胜了几场,输了几场、平了几场。
dp状态就很自然了:现在到了第\(i\)个队伍,现在有多少个没有配对的胜场、负场、平场,最少有多少个队伍比队伍\(0\)高。
那么我们考虑转移。
首先肯定是要枚举这个队伍的胜负平场数。
然后就要枚举平局的和之前的场次的配对个数。(正因为我没有枚举这个,而是所有的全都配对了,导致错了几个点。
那么最后的答案就是n,0,0,0。
还有一种方法。
我们换一种\(dp\)状态。
考虑\(dp(i,j,k,l)\)表示现在到了第\(i\)个队伍,有\(j\)个胜场,\(k\)个负场,最大平场数量为\(l\)。
那么还是枚举胜负平的场数abc,然后转移到\(dp(i+1,j+a,k+b,max(l,c))\)。
最后需要判断\(l\)不能超过\(4\times n-2\times j-2\times k\)。
因为不能一个单独的平场没有配对的。
然后就好辣。