[信息学奥赛一本通]1271：【例9.15】潜水员

这题其实是一个变种背包——二维费用背包

解题思路

将dp[i][j]看作氧气为i，氮气为j时的最小重量值，将dp数组所有值设为一个足够大的数，例如inf(整形最大)，将dp[0][0]设置为0，用于记录dp[ai][bi]的值，初始的时候只有当x=0,y=0时才停止，这时记录第一个值dp[3][36]=120。

然后当i=2时，到dp[3][36]停下，这时x+a[i]和y+b[i]分别都大于m和n，就得到dp[m][n]=120+129=249，然后再到dp[0][0]停下，记录下dp[10][25]=129。

然后当i=3时，到dp[m][n]直接停下，然后比较dp[m][n]和dp[m][n]+250的值，这时dp[m][n]值不变，之后一直到dp[3][36]停下，再到dp[0][0]停下，记录下dp[5][50]=250。

之后同理，最后一共记录了7个dp数组的值。

最后得出状态转移方程:dp[u][v]=min(dp[u][v],dp[x][y]+c[i])。

其中u=min(m,x+a[i]), v=min(n,y+b[i]),x的范围为m~0,y的范围是n~0。

OK，上代码