TPA算法实验作业

• TPA算法实验作业
  • 第一题：
  • 第二题：
  • 第三题：
  • 第四题：

第一题：

• 其实这题等价于背包问题求具体方案（不了解可以百度）。

  如果写过背包问题求具体方案这道题很容易解出，先看一下背包问题求具体方案的模板题。

  https://www.acwing.com/solution/content/2687/

  看完这篇博客不难看出这次的题目完全就是背包问题求具体方案换了个问法，只需要按价值排序后按背包问题求具体方案来做，以下是个人代码供参考

  

第二题：

• 思路：前缀和裸题没什么好说的（不知道什么是前缀和自己百度一下），也可以用老师说的动态规划思想来做（注意开long long，会爆int），以下是个人代码供参考

  

第三题：

• 奇技淫巧（骗分大法），可以找奇偶规律，能骗24分QAQ。

• 正经思路：区间DP问题，假设我是玩家1，对手是玩家2
  每一个格子是我作为一个玩家，设身处地地假设我本人或我的对手面对着区间(i,j)，作出最好的选择后能领先的最多分数。

  当我面对着(i,j)区间，我作为一个玩家每次只能选择i位置或j位置。
  如果我选择了i，那么我的对手将会获得(i+1,j)格子内的分数；
  而如果我选择了j，我的对手将获得(i,j-1)格子内的分数。
  而这(i+1,j)格子和(i,j-1)格子内有多少分数，是我站在对手的角度为他思考而最多能领先分数。

  敲黑板：只要我站在格子(i,j)在做判断，此时的我的身份可能是我自己，也可能是我在为想象的对手考虑！

  那么我站在这个区间，会选择i还是j呢？
  假如我选择i，那么我的对手会领先(i+1,j)格子内的分数，而我新吸收了i位置的分数，所以我会比我的对手领先a[i]-f(i+1,j)
  假如我选择j，那么我的对手会领先(i,j-1)格子内的分数，而我新吸收了j位置的分数，所以我会比我的对手领先a[j]-f(i,j-1)
  两者取其大即可。
  注：f(i,j)是DP表格中(i,j)位置的分数，即不论是我(玩家1)还是对手(玩家2)在这个格子作出选择后能领先的最多分数

  完成整张表之后，我怎么知道我（玩家1）能不能在对手(玩家2)也作出最好的选择的情况下还是领先呢？
  只要看DP(0,len(a)-1)的位置里的领先分数是否>=0就可以了，因为在动态规划更新的过程中，每一个格子都是我为自己，或者为对手设身处地思考得到的最佳分数。
  而我现在查看DP(0,len(a)-1)这个位置，就代表我在这个位置是拥有选择权的。而我(玩家1)确实在这个位置有选择权，因为我是全局先手。以下是个人代码供参考**

  

第四题：

• 思路：二维费用背包模板题，只需要像01背包一样做，只不过多一维表示容积，多一层for循环来判断是否超过当前容积即可以下是个人代码供参考