2212. 射箭比赛中的最大得分-动态规划算法-多背包问题转化

2212. 射箭比赛中的最大得分-动态规划算法-多背包问题转化

Alice 和 Bob 是一场射箭比赛中的对手。比赛规则如下：

Alice 先射 numArrows 支箭，然后 Bob 也射 numArrows 支箭。
分数按下述规则计算：
    箭靶有若干整数计分区域，范围从 0 到 11 （含 0 和 11）。
    箭靶上每个区域都对应一个得分 k（范围是 0 到 11），Alice 和 Bob 分别在得分 k 区域射中 ak 和 bk 支箭。如果 ak >= bk ，那么 Alice 得 k 分。如果 ak < bk ，则 Bob 得 k 分
    如果 ak == bk == 0 ，那么无人得到 k 分。

例如，Alice 和 Bob 都向计分为 11 的区域射 2 支箭，那么 Alice 得 11 分。如果 Alice 向计分为 11 的区域射 0 支箭，但 Bob 向同一个区域射 2 支箭，那么 Bob 得 11 分。
1
2
3
4
5
6
7

给你整数 numArrows 和一个长度为 12 的整数数组 aliceArrows ，该数组表示 Alice 射中 0 到 11 每个计分区域的箭数量。现在，Bob 想要尽可能 最大化 他所能获得的总分。

返回数组 bobArrows ，该数组表示 Bob 射中 0 到 11 每个 计分区域的箭数量。且 bobArrows 的总和应当等于 numArrows 。

如果存在多种方法都可以使 Bob 获得最大总分，返回其中 任意一种 即可。

示例 1：

输入：numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
输出：[0,0,0,0,1,1,0,0,1,2,3,1]
解释：上表显示了比赛得分情况。
Bob 获得总分 4 + 5 + 8 + 9 + 10 + 11 = 47 。
可以证明 Bob 无法获得比 47 更高的分数。

示例 2：

输入：numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
输出：[0,0,0,0,0,0,0,0,1,1,1,0]
解释：上表显示了比赛得分情况。
Bob 获得总分 8 + 9 + 10 = 27 。
可以证明 Bob 无法获得比 27 更高的分数。

对于这个多背包算法，说句实在的，还挺复杂的，解题代码如下：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* maximumBobPoints(int numArrows, int* aliceArrows, int aliceArrowsSize, int* returnSize){
   int  dp[aliceArrowsSize+1][numArrows+1];
   int t[aliceArrowsSize];

    for(int i=0;i<numArrows+1;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=aliceArrowsSize;i++){
        t[i-1]=aliceArrows[i-1];
       
         dp[i][0]=0;
        for(int j=1;j<=numArrows;j++){
             int need=aliceArrows[i-1]+1;
              if(j>=need){
                dp[i][j]=fmax(dp[i-1][j-need]+i-1,dp[i-1][j]);
            }
            else{
                dp[i][j]=dp[i-1][j];

            }
        

        }
            
       
       
    }
  
    for(int i=1;i<=aliceArrowsSize;i++){
        aliceArrows[i-1]=0;

    }
    for(int j=aliceArrowsSize;j>=1;j--){
        
        if(dp[j][numArrows]>dp[j-1][numArrows]){
           
        
            numArrows=numArrows-t[j-1]-1;

           
            aliceArrows[j-1]=t[j-1]+1;
          

        }
     
    }
    aliceArrows[0]=numArrows;

    


   *returnSize=aliceArrowsSize;
   return aliceArrows;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58