【Topcoder 10689】TheSoccerDivOne

题意:给\(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\)。

因为不能一个单独的平场没有配对的。

然后就好辣。

上一篇:分享基于分布式Http长连接框架--架构模型


下一篇:User-Agent 请求消息头