2021CCPC华为云挑战赛 部分题题解

CDN流量调度问题

题看了没多久就看出来是\(DP\)的题,然后就设了状态\(f[i][j]\)表示到前\(i\)个点时已经用了\(j\)个节点的最小总代价,结果发现转移时\(O(nm^2)\),但这样只会T掉的,于是就顺利应当的进入了DP优化的思维,奈何无论用上什么伎俩都好像有点不太奏效,以下给出暴力的代码:

rep(i,1,n)    rep(j,0,m)
            rep(k,1,min(j+1,t[i]))//枚举i的节点数量。
                f[i][j]=min(f[i][j],f[i-1][j+1-k]+a[i]/k+(a[i]%k?1:0));

发现难点就在于转移时,\(a[i]/k\)(向上取整)这个没法很好的处理....之后看来看题解,发现果然是在这里做文章的,由于是向上取整,所以不够倍数或者说是有余数的都加1,所以最优的情况下一定是对于每个点的\(a[i]\)而言它的总点数是\(a[i]\)的一个因子,这样既能减少总的时间又能节省更多的节点,所以我们这里枚举k时,只需要枚举\(t[i]\)的因子就行了于是复杂度就变成了\(O(nm\sqrt{t_i})\)正好在允许的范围内。...所以DP优化还要根据具体的转移情况而定,考虑每个题目的特殊性。

上一篇:「Gym102956F」Border Similarity Undertaking


下一篇:21.10.10模拟 魔方俱乐部