解题报告20230204

主要学习内容有：动态规划，字符串操作（在另外一篇文章里）

T1: P5322 [BJOI2019] 排兵布阵

首先题意是设定有n座城堡，s个玩家（不包括特殊玩家），此时每名玩家都有m名士兵，可以向城堡派一定数量的兵（每轮都一样），比赛采用1v1赛制，当一名玩家派遣的士兵数严格大于对手派遣士兵数的两倍时（即>=2ai+1）可占领城堡（可以获得城堡编号i的i值得分）。那现在有一位特殊玩家也有m个士兵，但他已经知晓了其他所有士兵的派兵策略，怎样可以获得最大得分。

那么我们就知道了如何派兵可以在1v1中战胜一名玩家，仔细想想，我们可以发现如果我们可以在一座城堡中战胜其中一名玩家，那么比这名玩家派兵数量少的都将被特殊玩家击败，那么得分就为被击败的玩家数量乘以该城堡编号i的i值得分。

所以题意转化为：有n座城堡，特殊玩家有m个代价，每座城堡有s个玩家，给定击败一名玩家所需的代价（2ai+1），可获得得分为被击败的玩家数量乘以该城堡编号i的i值得分。我们发现这就变成了一个分组背包问题

本题做法：先将每座城堡的玩家派的士兵数量排序，再分组背包

本题收获：为了排序每座城堡的玩家派的士兵数量，且可以二维数组排序，但输入时是输入一名玩家的的所有城堡的派兵策略，为了方便，我们需要变通输入方式，以下为代码。end

rd(s, n, m);
fz(i, 1, s){
    fz(j, 1, n){
        rd(fort[j][i]);
    }
}
fz(i, 1, n){
    sort(fort[i] + 1, fort[i] + s + 1);
    fz(j, 1, s){
        fort[i][j] = fort[i][j] * 2 + 1;
    }
}