• Ban or Pick, What‘s the Trick


    Bobo has recently learned how to play Dota2. In Dota2 competitions, the mechanism of banning/picking heroes is introduced, modified and simplified as follows for the sake of the problem:

    Suppose a game is played between two teams: Team A and Team B. Each team has a hero pool of nn heroes with positive utility scores a_1,\dots,a_na1​,…,an​ and b_1,\dots,b_nb1​,…,bn​, respectively. Here we assume all heroes in two teams' hero pool are distinct.

    The two teams then perform ban/pick operations alternately, with Team A going first. In one team's turn, it can either pick a hero for itself, or ban an unselected hero from the opponent's hero pool.

    After 2n2n turns, all heroes are either picked or banned. Each team then needs to choose at most kk heroes from all heroes it picked to form a warband and the score for the warband is calculated as the sum of utility scores over all heroes in it.

    Let s_A, s_BsA​,sB​ be the score of the warband formed by Team A and Team B, respectively. Team A wants to maximize the value of s_A-s_BsA​−sB​ while Team B wants to minimize it.

    Bobo wants to know, what should be the final value of s_A-s_BsA​−sB​, if both teams act optimally? He's not really good at calculating this, so he turned to you for help.

    An example of banning/picking heroes in Dota2. Source: TI10 True Sight

    Input

    The first line contains two integers n,k(1\leq n\leq 10^5,1\leq k \leq 10)n,k(1≤n≤105,1≤k≤10).

    The second line contains nn integers a_1,a_2,\dots,a_na1​,a2​,…,an​ (1\leq a_i\leq 10^8)(1≤ai​≤108), denoting the utility score of heroes for Team A.

    The third line contains nn integers b_1,b_2,\dots,b_nb1​,b2​,…,bn​ (1\leq b_i\leq 10^8)(1≤bi​≤108), denoting the utility score of heroes for Team B.

    Output

    Output an integer in one line, denoting the answer.

    Sample 1

    InputcopyOutputcopy
    2 1
    3 6
    2 4
    
    2
    

    Sample 2

    InputcopyOutputcopy
    4 1
    1 3 5 7
    2 4 6 8
    
    0
    

    Sample 3

    InputcopyOutputcopy
    4 2
    4 6 7 9
    2 5 8 10
    
    3
    1. #include<iostream>
    2. #include<algorithm>
    3. #include<map>
    4. #include<cstring>
    5. #include<vector>
    6. using namespace std;
    7. typedef long long ll;
    8. const ll INF = 0x3f3f3f3f3f3f3f;
    9. const int N = 1e5 + 10;
    10. const int K = 11;
    11. int n, k;
    12. int a[N], b[N];
    13. ll dp[2 * N][K][K];//双方操作总和,a选的英雄,b选的英雄
    14. //dp记录sa-sb
    15. int vis[2 * N][K][K];
    16. bool cmp(int a, int b)
    17. {
    18. return a > b;//从大到小排序
    19. }
    20. ll find(int s, int na, int nb)//s表示当前轮次进行了多少次操作,na表示A选择了几个英雄,nb表示B选择了几个英雄
    21. {
    22. //如果已经处理完所有的轮次,则返回0
    23. if (s > 2 * n) return 0;
    24. //如果之前已经计算过这个状态,则直接返回之前计算得到的结果
    25. if (vis[s][na][nb]) return dp[s][na][nb];
    26. vis[s][na][nb] = 1;
    27. //根据当前状态计算出A、B分别选择哪个英雄
    28. int ta = s / 2 - nb + na;
    29. int tb = (s + 1) / 2 - na + nb;
    30. //在奇数轮中,A先选择一个英雄,然后B再选择一个英雄
    31. if (s & 1)
    32. {
    33. int ta = ((s - 1) / 2 - nb) + na + 1;
    34. //在当前状态下,A不选择这个英雄
    35. dp[s][na][nb] = find(s + 1, na, nb);
    36. //如果A还没有选择k个英雄,并且ta小于等于n,则考虑选择这个英雄
    37. if (ta <= n && na < k) dp[s][na][nb] = max(dp[s][na][nb], find(s + 1, na + 1, nb) + a[ta]);
    38. return dp[s][na][nb];
    39. }
    40. //在偶数轮中,B先选择一个英雄,然后A再选择一个英雄
    41. else
    42. {
    43. int tb = (s / 2 - na) + nb + 1;
    44. //在当前状态下,B不选择这个英雄
    45. dp[s][na][nb] = find(s + 1, na, nb);
    46. //如果B还没有选择k个英雄,并且tb小于等于n,则考虑选择这个英雄
    47. if (tb <= n && nb < k) dp[s][na][nb] = min(dp[s][na][nb], find(s + 1, na, nb + 1) - b[tb]);
    48. return dp[s][na][nb];
    49. }
    50. }
    51. int main()
    52. {
    53. memset(dp, -1, sizeof dp);//初始化dp数组为-1
    54. scanf("%d %d", &n, &k);
    55. for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a + 1, a + n + 1, greater<int>());//从大到小排序
    56. for (int i = 1; i <= n; i++) scanf("%d", &b[i]); sort(b + 1, b + n + 1, greater<int>());
    57. //从状态(1,0,0)开始计算
    58. find(1, 0, 0);
    59. cout << dp[1][0][0] << endl;//输出最终的结果
    60. }

     

  • 相关阅读:
    Science:大脑中睡眠的相互关联原因和结果
    R语言分析:如何轻松地把数据分为三、四、五等份?
    STM32 SPI对存储芯片发送写是能命令后一直忙等待
    【时间序列预测】Informer论文笔记
    手把手教你在项目中引入Excel报表组件
    xshell修改字体大小
    常用接口测试及接口抓包常用的测试工具
    Unity Xlua热更新框架(六):场景管理
    linux下nginx安装与配置说明
    【web-避开客户端控件】(2.3.1)收集使用数据:浏览器扩展技术、攻击浏览器扩展的方法
  • 原文地址:https://blog.csdn.net/GF0919/article/details/132716740