Python动态规划——以“codeJan与青蛙”为例

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

题目描述

????????codeJan喜欢观察世界。有一天，codeJan发现一个非常奇怪的现象。有一些年轻的青蛙聚集在一条直线上的某些位置上，同一个位置可能有多个青蛙。这些青蛙每次只会向前跳一米，并且每只青蛙每跳一次都会发出’WA’的一声。codeJan想在一些青蛙的位置上放置黑洞来收集全部的青蛙。在黑洞位置上的青蛙会直接掉进黑洞中不会发出任何叫声，其余的青蛙经过若干次跳跃都会掉进在它前面的最近的黑洞。因为WA类似WrongAnswer，所以codeJan想要知道他合理地安排黑洞的位置，最少可以听到多少声WA？在听到最少声WA时，需要准备的每个黑洞的容量至少为多少？黑洞的容量体现为可以容纳的青蛙的最大数量，所有黑洞的容量应该都相同。? ? ?

输入描述

????????第一行一个正整数T≤20表示测试组数。每组测试样例的第一行是两个正整数n,m，分别表示存在青蛙的位置和可以放置黑洞的数量。接下来n行，每行包含两个正整数a[i],b[i]分别表示第i组青蛙的位置(单位：米)和这个位置上青蛙的数量。

输出描述

????????对于每组测试用例用一行输出两个正整数分别表示最少可以听到多少声WA和黑洞的最少容量。用空格隔开，行末无空格。??

示例1

2 
3 1 
1 1 
2 2 
3 3 
3 2 
1 1 
4 2 
2 3

输出

8 6
3 4

?备注：对于第一个样例，只能放在 1 位置，因此听到的 WA 的次数为：1*0+2*1+3*2=8，所有青蛙汇聚在一次，容量至少为 6。
对于第二个样例，可以放在 1 和 4 位置，因此听到的 WA 的次数为：1*0+3*1+2*0=3，1 位置和 2 位置的青蛙汇聚在一 起，需要容量为 4；4 位置的青蛙单独在一起，需要容量为 2。因此容量至少为 4

思路

? ? ? ? ?首先根据青蛙每次向前跳一米和青蛙经过若干次跳跃都会掉进在它前面的最近的黑洞，因此先确定一条直线的正方向为青蛙向前跳的方向，在这我将青蛙朝左跳为正方向。因为青蛙都是向前跳直到跳进离它最近的黑洞中，因此先把所有的青蛙按照位置关系从大到小进行排序。首先对以下几个变量进行定义：

dp[i][j] ：用j个黑洞收集前i个位置的青蛙蛙叫次数的最小值

cost[k][i]：位置k到位置i的所有青蛙全部被位置k上的黑洞所收集到的蛙叫次数（因此这里的k一直小于等于i）

sum[i][j]：用j个黑洞收集前i个位置的青蛙最大数量

通过枚举第j个黑洞的位置k，对dp表不断进行更新，更新dp过程中记录第j个黑洞的收集青蛙数量以及上一个状态时的青蛙数量并进行比较更新次数。因此可以得到状态转移方程：

?

代码

第一段代码：对输入参数进行赋值并创建dp表。这里首先定义lst = [(0,0)]是为了进行统一，实际上用不到。之后利用zip函数将青蛙位置与数量拆分成两个数组a,b。

T = int(input())
for _ in range(T):
    n,m = map(int,input().split())
    lst = [(0,0)]
    for _ in range(n):
        x,y = map(int,input().split())
        lst.append((x,y))
    a,b = zip(*sorted(lst))
    dp = [[1e12] * (n + 1) for _ in range(n + 1)]
    sum = [[0] * (n + 1) for _ in range(n + 1)]
    cost = [[0] * (n + 1) for _ in range(n + 1)]

第二段代码：共分为四段循环。

????????第一段循环是因为再第一段代码中为了统一首先增加了(0,0)，因为在这里将dp表的第一行全部变成0不影响接下来的状态转移。

????????第二段循环是在1个黑洞的情况下对dp表的第一列进行更新，由于青蛙只能向前跳并且要收集所有青蛙，因此第一个青蛙所在的位置必须放置一个黑洞。按照思路在更新dp表的同时记录每个位置的收集青蛙数量，由于这段循环是在1个黑洞的情况下进行更新dp表，因此不用进行比较。相当于在给dp表赋初值。

? ? ? ? 第三段循环是更新cost表，记录位置i到位置j的所有青蛙全部被位置i上的黑洞所收集到的蛙叫次数。

? ? ? ? 第四段循环是更新dp表，这里则是整个动态规划的关键。在状态转移方程中，dp[k - 1][j - 1]代表在前k - 1个位置中有j - 1个黑洞收集的蛙叫次数，对于我所需要的一整段还缺少位置k到位置i中1个黑洞手机的蛙叫次数数据，而这一段则是先前定义的cost变量，cost[k][i]则是记录了位置k到位置i中所有青蛙被位置k的黑洞所收集的蛙胶次数数据，因此等式两边相等，得到状态转移方程。再通过比较大小进行更新dp表，最后得到的dp[n][m]则是答案，输出即可。

    for i in range(n + 1):
        dp[0][i] = 0
    for i in range(1, n + 1):
        dp[i][1] = dp[i - 1][1] + (a[i] - a[1]) * b[i]
        sum[i][1] = sum[i - 1][1] + b[i]
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            cost[i][j] = cost[i][j - 1] + (a[j] - a[i]) * b[j]
    for i in range(2, n + 1):
        for j in range(2, m + 1):
            for k in range(2, i + 1):
                if dp[i][j] > dp[k - 1][j - 1] + cost[k][i]:
                    dp[i][j] = dp[k - 1][j - 1] + cost[k][i]
                    sum[i][j] = max([sum[k - 1][j - 1],sum[i][1] - sum[k - 1][1]])
    print(dp[n][m],end = ' ')
    print(sum[n][m])

完整代码如下。

T = int(input())
for _ in range(T):
    n,m = map(int,input().split())
    lst = [(0,0)]
    for _ in range(n):
        x,y = map(int,input().split())
        lst.append((x,y))
    a,b = zip(*sorted(lst))
    dp = [[1e12] * (n + 1) for _ in range(n + 1)]
    sum = [[0] * (n + 1) for _ in range(n + 1)]
    cost = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[0][i] = 0
    for i in range(1, n + 1):
        dp[i][1] = dp[i - 1][1] + (a[i] - a[1]) * b[i]
        sum[i][1] = sum[i - 1][1] + b[i]
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            cost[i][j] = cost[i][j - 1] + (a[j] - a[i]) * b[j]
    for i in range(2, n + 1):
        for j in range(2, m + 1):
            for k in range(2, i + 1):
                if dp[i][j] > dp[k - 1][j - 1] + cost[k][i]:
                    dp[i][j] = dp[k - 1][j - 1] + cost[k][i]
                    sum[i][j] = max([sum[k - 1][j - 1],sum[i][1] - sum[k - 1][1]])
    print(dp[n][m],end = ' ')
    print(sum[n][m])

感想

? ? ? ? 本题代码以及思路均由我的指导老师黄老师所提供，在一天的理解之后想要记录下来这类题目的一个思路。本题是一次内部赛中老师所选的题目，当时看到这道题时就想起了蓝桥系统上的居民集会，当时在遇到这道题时就没有ac，因此青蛙这道题同样没有ac。在理解完老师给的思路后，为了加深印象自己重新写了一遍整个代码。但是在写完之后提交一直是50%的通过率，令我百思不得其解。之后就在老师给的代码找不同，找了半天发现是dp表赋初值时我赋的是1e9，也是习惯用这个参数了，起初并没有在意，但我改掉这个参数后就通过了。再次读题发现题目数据确实最大值可以达到1e12次。所以题目是不会白给的，做题前还是要仔细读题的。在做青蛙这道题目时要求收集的蛙叫次数最少，首先想到的是暴力枚举，枚举所有黑洞的排列情况再分别统计蛙叫次数。若在OI赛制中，没有思路时，对于容量小的一部分测例则是可以通过暴力枚举来得到一定的分数。这也算是OI赛制中的一个小技巧吧。若要通过全部测例，本题则是需要用到动态规划，关于动态规划的题经常会看到这样一条评论：dp难度无上限。其实在更新dp表的过程中就会发现状态转移方程其实本质上就是在重复做一件事情，只要找到其中的重复性去推导整个过程，递归的本质也是如此，而且代码及其简单，只不过一个是正推一个是逆推。之后为了趁热打铁，我去做了蓝桥上居民集会这道题，理解完题目意思时稍微转化一下发现与青蛙题几乎一模一样，只是正方向相反而已。但之后还是遇到了内存超限问题，可能是我的代码还没有最优化，平常遇到内存超限的次数还是挺少的。

?