笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

「签到题」 CF1354F Summoning Minions

posted on 2020-05-19 10:58:26 | under 题解 |

upd: 改了错别字

旁白:这个 F 怎么也这么签啊?


盲猜这个游戏是炉石

赛场上一眼背包,发现大概是 $O(\max\{a_i,b_i\}\cdot nk^2)$ 的就弃掉了。然后考虑贪心。考虑这么一个比较自然的想法,就是先找出前 $k-1$ 个来,然后 $n-k$ 个加一个删一个,最后再把 $1$ 个加进来。不难知道这样一定可以做出最优的决策。

那么考虑怎么搞这三部分。

第一部分可以背包,$f_{i,j}$ 表示前 $i$ 个随从找出了 $j$ 个放进第一个部分的最大价值。注意这个地方有一个代价提前计算的思想。就是说考虑如果把随从 $z$ 在前 $k-1$ 个里的第 $j$ 位召唤出来,那么放到后面应该是产生 $(k-1)\cdot b_z$ 的贡献,现在就只有 $(j-1)\cdot b_z$ 的贡献,于是有

$$ f_{i,j}=\max\left\{f_{i-1,j-1}-(k-j)\cdot b_i+a_i,f_{i-1,j}\right\} $$

然后一个小细节就是显然必须要按照 $a_i$ 降序且 $b_i$ 升序来进行排序,同时由于是对 $a_i$ 来 $dp$,所以应该让 $b_i$ 为第一关键字。

第二、三部分考虑合起来做。即考虑枚举最后一个随从,那么剩下的元素就一定是按照 $b_z$ 升序排序,因为他们加入就会被立即删掉。

但这样会发现 WA ON 2。冷静一下就会发现最后一个元素由于也要计算其 $a_i$ ,所以应该和前面的 $k-1$ 个等价,换言之最后在剩下的元素里贪出最后一个位置放的随从是不对的。观察数据范围很小,于是可以枚举最后一个位置放哪个随从,对于不同的最后一个位置分别做前两部分。不难知道这样是对的。

这样最后复杂度 $O(T\cdot n^2k)$,可以通过本题。

瞎扯1:

这么看来这个复杂度还是很合理的?$75^4$ 大概在 $3e7$ 左右。

瞎扯2:

实际上场上写的时候并没有细想第一部分到底该怎么排序,那反正就是要么 $a_i$ 做第一关键字要么 $b_i$ 做第一关键字。看着当时似乎没多少人过 F 就选择 $2!$ 枚举了一下这两种排法(

瞎扯3:

为什么这场比较正常的题 (E 以及 E 之后) 都这么无聊但是代码这么麻烦?反正我写的挺麻烦的。


int T ;
struct minion{
    int a, b, id ;
}base[N], tmp[N] ;
int n, k ;
int cnt ;
int ans ;
int lst ;
int ud[N] ;
int fin[N] ;
int quq[N] ;
int qaq[N] ;
int qwq[N] ;
int f[N][N] ;
int pre[N][N] ;

bool comp(minion x, minion y){
    return x.b == y.b ? x.a > y.a : x.b < y.b ;
}
bool cop(minion x, minion y){ return x.b < y.b ; }
int main(){
    cin >> T ;
    while (T --){
        cin >> n >> k ; ans = 0 ;
        for (int i = 1 ; i <= n ; ++ i)
            base[i].a = qr(), base[i].id = i, base[i].b = qr() ;
        sort(base + 1, base + n + 1, comp) ;
        fill(fin, fin + n + 1, 0) ;
        for (int z = 1 ; z <= n ; ++ z){
            memset(f, -63, sizeof(f)) ;
            fill(ud, ud + n + 1, 0) ;
            f[0][0] = 0 ; cnt = 0 ;
            for (int i = 1 ; i <= n ; ++ i){
                for (int j = 0 ; j <= k - 1 ; ++ j){
                    int tmp = base[i].b * (j - k)  ;
                    if (!j || i == z)
                        f[i][j] = f[i - 1][j], pre[i][j] = 0 ;
                    else {
// cout << i << " " << j << " " << f[i - 1][j] << " " << f[i - 1][j - 1] + base[i].a + tmp << '\n' ;
                        if (f[i - 1][j] > f[i - 1][j - 1] + base[i].a + tmp)
                            f[i][j] = f[i - 1][j], pre[i][j] = 0 ;
                        else f[i][j] = f[i - 1][j - 1] + base[i].a + tmp, pre[i][j] = 1 ;
                    }
                }
            }
            int p = n, q = k - 1 ;
            while (p && q){
                if (!pre[p][q]) -- p ;
                else qaq[q] = p, ud[base[p].id] = 1, -- q, -- p ;
            }
//            debug(q) ;
            debug(ud, 1, n) ;
            for (int i = 1 ; i <= n ; ++ i)
                if (!ud[base[i].id] && i != z) qwq[++ cnt] = i ;
            int res = 0, gz = 0 ;
            for (int j = 1 ; j <= cnt ; ++ j) tmp[++ gz] = base[qwq[j]] ;
            sort(tmp + 1, tmp + gz + 1, cop) ;
            for (int j = 1 ; j <= gz ; ++ j) res += (k - 1) * tmp[j].b ;
            for (int j = 1 ; j <= k - 1 ; ++ j)
                res += base[qaq[j]].a + (j - 1) * base[qaq[j]].b ;
            res += base[z].a + base[z].b * (k - 1) ;
            debug(res) ;
//            for (int j = 1 ; j <= k - 1 ; ++ j)
//                cout << base[qaq[j]].id << " \n"[j == k - 1] ;
            if (res >= ans) {
                ans = res, lst = z ;
                for (int i = 1 ; i <= k - 1 ; ++ i) quq[i] = qaq[i] ;
                for (int i = 1 ; i <= cnt ; ++ i) fin[i] = qwq[i] ;
            }
        }
//        debug(ans) ;
//        debug(cnt) ;
        cout << k + 2 * cnt << '\n' ;
        for (int i = 1 ; i <= k - 1 ; ++ i)
            cout << base[quq[i]].id << ' ' ;
        for (int i = 1 ; i <= cnt ; ++ i)
            cout << base[fin[i]].id << ' ' << -base[fin[i]].id << ' ' ;
        cout << base[lst].id << "\n" ;
    }
    return 0 ;
}/*
1
5 2
3538 43176
24258 77210
92123 70606
44495 37855
65913 67119
291273
8
3 4 -4 2 -2 1 -1 5
4 2 -2 5 -5 1 -1 3
*/