JLOI2010 世界杯租房

数据很水,偷偷看了下好像 T \leqslant 100

嗯,DP+输出方案。记得为了字典序最小我们要倒着DP。。

然后没了。。别写龊了写炸复杂度就好。

O(Tmn^2)

 

 

JLOI2008 CODES

一天半,唉。。真该AFO了。

首先考虑我们可以DP,设状态 dp[i][j] 表示 第 i 个字符串  还需要匹配长度为 j 的前缀   可以得到的最短答案。

转移:

转移就是枚举一个字符串 i_0 来与之匹配。记忆化搜索非常好写。注意讨论两种情况:

  1. i_0比当前前缀长
  2. i_0比当前前缀短

用 dp[i0][?] + 匹配长度 去更新dp[i][j]。(?是因为我懒得讨论了……代码里有)

数据范围很小,暴力匹配即可。

注意事项:

第一个细节就是字符串可以重复利用;

第二个细节是让dp[i][0]=0 其余为 +\infty

第三个细节就是最后统计答案和DP过程中别忘记比较字典序。

字典序:

 answ[i][j] 保存当前 dp[i][j] 对应的具体方案,

更新 dp[i][j] 顺便更新 answ[i][j] 即可。

每次遇到 dp[i0][?]+len  dp[i][j] 相等的情况,判定字典序,然后更新 answ[i][j] 即可。

最后的答案是 dp[i][len[i]]

O(\text{跑得过})

头插DP指北

UPD:排版已挂。先去洛谷看吧,这边待修。

洛谷ID:GNAQ

 

UPD:我稍微改了一下封面图片,现在它成了真 · 插头DP了 😕

插头DP的概念(据我不可靠考证)最早出现在08年CDQ的论文中,而此类题目早在04年前后就已经存在。

(***下面假设聚聚们都会了状压DP……)


1.什么是插头DP

插头DP (PlugDP ,By yhzq),也就是一类基于连通性的状态压缩动态规划,是用状压DP处理联通问题的强劲武器。

常见的类型有棋盘插头DP和CDQ论文里的两个非棋盘上的模型。

常见的联通问题:多回路问题、路径问题、简单回路问题、广义路径问题、生成树问题


2.插头DP的大致思路


2.1 划分阶段

大家都知道了这是基于联通性的状压DP,所以本质上还是状压DP。

一般设dp[i][j][state](i,j)位置,状态为mathrm{state}的方案数(或者代价,等等让你求的东西……)

所以我们状压什么呢?轮廓线。

DP求解棋盘问题是逐格转移的。所以已经转移过的格子和没转移过的格子被一个折线分成了两半儿。这个折线就是轮廓线。

@远航之曲的简洁解释:已决策格子和未决策格子的分界线)

就这个蓝线(现在转移的格子是第3行第3个)。

插头又是什么呢?一个格子有四个插头,一个存在的插头表示在它代表的方向上能与相邻的格子连接(联通)。不存在就不能。

为什么要引入插头?要求一个回路,也就意味着最后所有的非障碍格子通过插头连接成了一个连通块,因此转移时需要记录格子的连通情况。

我们递推的时候就是依据轮廓线上的插头存在性,求出所有能转移到的合法状态

显然回路问题中一个格子恰好有两个插头,一个是“进来”的一个是“出去”的。


2.2 记录状态

最小表示法

所有的障碍格子标记为 0 ,第一个非障碍格子以及与它连通的所有格子标记为 1 ,然后再找第一个未标记的非障碍格子以及与它连通的格子标记为 2 ……重复这个过程,直到所有的格子都标记完毕。比如连通信息((1,2,5),(3,6),(4)) 表示为{ 1,1,2,3,1,2 }

(还有一种最小表示法,即一个连通块内所有的格子都标记成该连通块最左边格子的列编号。)

括号表示法

【性质】轮廓线上从左到右 4 个插头 a, b, c, d,如果 a, c 连通,并且与 b 不连通,那么 b, d 一定不连通。这个性质对所有的棋盘模型的问题都适用。证明详见CDQ论文。

“两两匹配”,“不会交叉”这样的性质,我们很容易联想到括号匹配。

将轮廓线上每一个连通分量中左边那个插头标记为左括号,右边那个插头标记为右括号,由于插头之间不会交叉,那么左括号一定可以与右括号一一对应,这样我们就可以使用 3 进制, 0 表示无插头, 1 表示左括号插头, 2 表示右括号插头,记录下所有的轮廓线信息。不妨用#表示无插头,那么上面的三幅图分别对应的是 (())#(),(()#)(),(()###) ,即 (1122012),(1120212),(1120002) ,这种表示方法称为括号表示法。

状态的编码

对于最小表示法,编码最简单的方法就是表示成一个 n+1 位的 p 进制数, p 可以取能够达到的最大的连通块标号加 1 。在不会超过数据类型的范围的前提下,建议将 p 改成 2 的幂,因为位运算比普通的运算要快很多。

如需大范围修改连通块标号,最好将状态 O(n) 解码到一个数组中,修改后再 O(n) 计算出新的 p 进制数,而对于只需要局部修改几个标号的情况下,可以直接用 (x ;mathrm{div}; p^{i-1} ) ;mathrm{mod}; p 来获取第 i 位的状态,然后 +k times p^{i-1} 直接对第 i 位进行修改。


2.3 转移状态

首先,因为逐行递推要讨论的情况还是比较难处理的,除非要求解的问题特别适合这样做,要不然我们一般使用逐格递推,这样可以方便讨论情况。

一般来说轮廓线上有不少状态都是无用的,而且一般来说插头DP的状态数很多,所以我们使用一个技巧来加速,那就是,我们用一个线性数据结构(我愿意开一个/模拟一个vector)来存储状态,每次读取上一格的所有合法状态扩展,而不是xjb枚举状态来扩展。

然后,我们来研究一下怎么转移。我们看一种题型吧。

给你一个 m times n 的棋盘,有的格子是障碍,问共有多少条回路使得经过每个非障碍格子恰好一次。

m, n \leqslant 12

1.新建一个连通分量

这个情况只出现在转移位置的轮廓线上没有下插头和右插头。

如图。然后我们只有一种转移方式就是当前格做右插头和下插头。

括号表示法就是新建一对紧挨着的左右括号。最小表示法就直接解码重编一下。

2.合并两个连通分量

如果当前轮廓线上既有右插又有下插,那你只能当前格做左插和上插,要不然就不是回路了。

然后如果右插和下插联通,那这种情况只能是在最后一个非障碍格是合法的。

不连通的话,当然这样做会把他们变联通,看图:

括号表示法里就直接删一对括号,最小表示法还是解码重编。

3.保持原来的连通分量

当轮廓线上只有下插或者右插,就只能当前格做一个左插/上插来满足回路性质,剩下一个插头是随便安排的。

图:

括号表示法的话就把下插/右插对应的括号移到你加的插头上就行了。

最小表示法也类似,把下插/右插位置的记号移到你加的插头对应位置就行(因为是延续了一个连通分量)。

注意当从一行的最后一个格子转移到下一行的第一个格子的时候,轮廓线需要特殊处理。这个看代码最好解释了。

(还要多啰嗦一句,一般状态编码的左右和轮廓线的左右是反着对应的……也就是编码最右面一位是对应轮廓线最左面格子)

一个小优化

有时候你转移的时候有可能从两个不同状态转移出同一个状态,这个时候我们用hash优化它就好了。hash表的实现用挂表法就行。

还有提取每个插头状态的时候我们可以预处理一个对应bit的数组,然后用上文提到的解码方式去解码。

这儿还是曲神@远航之曲的trick,他讲的很明白。


然后我们就讨论完了插头DP的第一道入门题该怎么做,题目提交在这儿:1519. Formula 1

我真的是抄的曲神的代码,曲神码风和实现都太棒了!


··
·····


state是表示状态,dp表示方案数。这里用了滚动数组来优化空间(pre,cnt来滚动)


bits是一个方便提取插头的数组。比如bits[3]=6,那提取第三个格子上面和左面的插头(分别叫做is_d和is_r)就是state>>bits[3-1]和state>>bits[3]


我们存储状态是四进制,括号表示法。1表示(,2表示) 。


hash表的内部实现你可以看到就是一个链表。(struct hash_table)


·····


因为可能最后一格也有障碍,所以要记录一下最后一个无障碍格子(endx,endy)


··


添加状态压进hah()函数里了。


·

·

·····


一开始要初始化dp(0,0)=1


·


77行,这是为了转移到下一行的时候处理第一个格子的is_r插头(建议在纸上模拟一下)


····


case 0:有障碍。

case 1:

case 2:

case 3:

case 4:(要改插头)

case 5:(要改插头)

case 6:(要改插头)

case 7:形成一个回路。只有最后一个格子才能形成一个回路。

P.S.为了做上面那个效果我拿Elementary Editor搞了半小时……

To be continued……

再来一道毒题 P3886 [JLOI2009]神秘的生物

唉。这题我写了差不多四天……还是真的菜。

首先说明的是这份代码来自vawait大佬 (肽聚了,写了无数插头DP……)

这道题还有一个很有意思的背景:

仔细想想你会发现SRM312好像是06年的比赛……

JLOI居然抄原题,差评

还有就是其实经过我的深刻反思,我意识到……

原题卡好几天!……

唉 我应该把论文和课件都看一遍的TAT

有一种策略就是我们可以只转移有左插和上插的格子。可惜其实这是很不对的一个策略,你没法应付像这样:

真令人头秃。那怎么办呢? 🙄

一些注意事项

首先你会发现,因为四个插头都是本质相同的,所以我们大可以用一个插头去概括它,也就是说,本题所谓的轮廓线是这样的:

也就是我们只需要保存 n 个格子的最小表示就可以转移了。稍加分析可以得到我们需要八进制来表示这么多格子的最小表示。


转移状态

按照一贯的套路我们又要讨论如何转移状态。基于对联通信息的维护,我们会有:

1.当前格无插头

2.当前格有插头

2.1 当前格属于“新建一个联通分量”

2.2 当前格加入之前的联通分量

所以一共有三种转移。

1非常好做。去掉即可。

2.1 非常好做,我们可以用 7 来表示新建的联通分量

2.2 从vawait大佬那里看到了一个实现上的技巧就是让当前的最小表示等于 mathrm{max(Dplug,Rplug)} 。然后让所有最小表示为 mathrm{min(Dplug,Rplug)} 的也等于它。


判定状态合法性

这个题和之前的不一样,因为答案并不是最后更新,转移完之后状态也都不一定是合法的。

所以hash之前应该先判一下状态的合法性

1如果没有下插,或者下插(也就是当前格的上面一格)与轮廓线上其他格联通,那这样转移是合法的,反之一定不合法。

2.1和2.2是一定合法的。


更新答案

hash之前要重新编码,编码完之后如果当前轮廓线上有一个或零个联通分量都是满足题目要求的状态,可以更新答案。


hash

还是和之前一样。不过我从vawait的代码里get到一个卡空间的技巧,就是把dp状态也压进hash表里。感觉也不难写。


重新编码

思路还是挺简单的。唯一需要合并联通分量的地方2.2也已经提前处理好了。

#洛谷 P1860 新魔法药水

神奇的DP

大概是用DP预处理要预处理的内容

然后用DP预处理

最后DP背包跑答案

 

卡了我很久有必要详细讲一下

题目描述

商店里有N种药水,每种药水都有一个售价和回收价。小S攒了V元钱,还会M种魔法,可以把一些药水合成另一种药水。他一天可以使用K次魔法,问他一天最多赚多少钱?

输入输出格式

输入格式:

第一行四个数N、M、V、K

接下来N行,每行两个数,表示药水的售价和回收价。

接下来M行,每行若干个数,第一个数表示魔法的成品,第二个数是原料的种数,接下来为各种原料的编号

输出格式:

一个数,表示小S的最大利润

·

N<=60 M<=240

V<=1000

k<=30

我们先考虑这是个背包

然后很自然的只需要求每个物品的min 购买价,然后二位费用xjb转移就可以得出答案

DP求这个部分.

因为有魔法,所以设计状态dx[i][j]表示物品i在当前用了j次魔法的情况下最小的购买价,这样才能当做背包来DP

dx怎么求呢?也不好求,所以这就是卡我的地方,我一开始还以为是DFS求

 

厚颜无耻的看题解……

你需要在枚举每个魔法w的时候都dp处理出 第w个魔法所需的前x个物品 用y次魔法 可以得到的最小购买价

设计状态ori[x][y]表示这样,每次枚举了一个魔法w都要求一次ori,注意y≤枚举的魔法次数

然后DP一波ori,这个很简单,写过几道提高水平的DP就会求

然后用ori[w需要的物品总数][枚举魔法次数-1]更新dx[w产成品][枚举的魔法次数]

·

这样我们就有了dx

xjb背包即可.XXXD

JZOJ 3808 | Luogu2103 道路值守

题目描述

Z-Kingdom有着四通八达的现代化交通。时值独立庆典之际,随着来自周边国家旅客的日益增多,犯罪行为也悄无声息开始滋长起来。

特别任务支援科的警察们从总部收到了关于调查伪装在游客中的犯罪分子的请求。通过调查,他们得到了一张地图,记载了Z-Kingdom内每一条道路的长度。

显然,为了减少犯罪行为被发现的可能性,犯罪分子总是会选择最短的路径来行动。为了方便安排人手和推测犯罪分子采取的路线,他们希望得知任意两个地点之间,有多少条犯罪分子可能会选择的道路。

输入输出格式

输入格式:

第一行,包含两个整数N,M,表示Z-Kingdom内的地点数和道路数。

接下来N行,每行包含三个整数x,y,z,表示道路连接的两个不同地点的标号,以及道路的长度。道路是双向的。

两个不同地点之间不会有超过一条道路。

输出格式:

输出一行,包含 N (N-1)/2 个整数

其中表示 x 号地点到 y 号地点之间有多少条犯罪分子可能会选择的道路。

先Floyd求出最短路

对于每一个点i:

{

枚举所有点j ,确保i,j联通,且i,j不是一点。

然后检查有多少点k与j有连边,且在i-j的最短路disi,j上。(也就是检查从i到j有多少条满足disi,j上且与j相连

       esumj=∑k1     k∈(g[k][j]!=0 && dis[i][k]+g[k][j]==dis[i][j])

最后考虑DP

枚举一个终点j,再枚举一个k,如果k在i-j的最短路上,那么esum[k]个方案计入C[i][j]。(有esumk条边可以到k点,在最短路上可以选k点,所以要计入方案数目)

}

#洛谷P2258 子矩阵

不看题解写不出来系列……

第一篇状压DP。

题目描述

给出如下定义:

  1. 子矩阵:从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵(保持行与列的相对顺序)被称为原矩阵的一个子矩阵。

例如,下面左图中选取第2、4行和第2、4、5列交叉位置的元素得到一个2*3的子矩阵如右图所示。

9 3 3 3 9

9 4 8 7 4

1 7 4 6 6

6 8 5 6 9

7 4 5 6 1

的其中一个2*3的子矩阵是

4 7 4

8 6 9

  1. 相邻的元素:矩阵中的某个元素与其上下左右四个元素(如果存在的话)是相邻的。
  2. 矩阵的分值:矩阵中每一对相邻元素之差的绝对值之和。

本题任务:给定一个n行m列的正整数矩阵,请你从这个矩阵中选出一个r行c列的子矩阵,使得这个子矩阵的分值最小,并输出这个分值。

PJ比TG难系列。

dfs一下选哪些行,处理一下前缀和,然后按照列DP一下就行了。

 

#洛谷 P1066 2^k进制数

题目描述

设r是个2^k 进制数,并满足以下条件:

(1)r至少是个2位的2^k 进制数。

(2)作为2^k 进制数,除最后一位外,r的每一位严格小于它右边相邻的那一位。

(3)将r转换为2进制数q后,则q的总位数不超过w。

在这里,正整数k(1≤k≤9)和w(k<W< span>≤30000)是事先给定的。

问:满足上述条件的不同的r共有多少个?

我们再从另一角度作些解释:设S是长度为w 的01字符串(即字符串S由w个“0”或“1”组成),S对应于上述条件(3)中的q。将S从右起划分为若干个长度为k 的段,每段对应一位2^k进制的数,如果S至少可分成2段,则S所对应的二进制数又可以转换为上述的2^k 进制数r。

例:设k=3,w=7。则r是个八进制数(23=8)。由于w=7,长度为7的01字符串按3位一段分,可分为3段(即1,3,3,左边第一段只有一个二进制位),则满足条件的八进制数有:

2位数:高位为1:6个(即12,13,14,15,16,17),高位为2:5个,…,高位为6:1个(即67)。共6+5+…+1=21个。

3位数:高位只能是1,第2位为2:5个(即123,124,125,126,127),第2位为3:4个,…,第2位为6:1个(即167)。共5+4+…+1=15个。

所以,满足要求的r共有36个。

输入输出格式

输入格式:

输入只有1行,为两个正整数,用一个空格隔开:

k W

输出格式:

输出为1行,是一个正整数,为所求的计算结果,即满足条件的不同的r的个数(用十进制数表示),要求最高位不得为0,各数字之间不得插入数字以外的其他字符(例如空格、换行符、逗号等)。

(提示:作为结果的正整数可能很大,但不会超过200位)

上来给了题解了,好贴心QAQ

第一要用高精度

第二,让你构造一个2k进制的,w/k位的(w的划分残余不考虑)数,且左面一位严格小于右面一位。

我们考虑递推,可以先打一个表

那么设p[i][j]表示从右向左数i位,最高位(最左面)的数最小为j , 可以构成的2k进制数的个数。 (最高位不为0)

那么,有两种转移。一是添加这个最小的数j,那从p[i-1][j+1]转移 (后面i-1位最小取j+1,由此计算可以构成的2k进制数的个数)

二是最高位数字比j大,从p[i][j+1]转移。

那么,看这个

考虑样例k=3 , w=7 的情况,串w肯定不能被完全分割,所以剩下一位,可以取0 ~ 2w%k -1 这样。

那就统计一发答案,最高位取i的时候需要的答案是p[w/k][i+1]这是肯定的。

然后考虑不完全取,ans+= ∑ p[i][1] (2<=i<=w/k)

但是,我们再来考虑这个样例:

k=2,w=8  这四位并不能完全用完。

那么显然最多可以有2k-1位。 (e.g. 当k=2时,位数最多时的方案是123,不存在1234或234或345等等,当k=3时,位数最多时的方案是1234567),也就是说,只需要加一下1~2k-1位的方案p[位数][1]就可以了。

那么就来推一波

然后写一个重载运算符的BNUM类

然后就行了,这是所有代码,注意readint

 

#洛谷 P1026 统计单词个数

垃圾题……照样处理一发区间[i,j]有多少单词然后枚举区间起点i转移就行了。

 

题目描述

给出一个长度不超过200的由小写英文字母组成的字母串(约定;该字串以每行20个字母的方式输入,且保证每行一定为20个)。要求将此字母串分成k份(1<k<=40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。当选用一个单词之后,其第一个字母不能再用。例如字符串this中可包含this和is,选用this之后就不能包含th)。

单词在给出的一个不超过6个单词的字典中。

要求输出最大的个数。

输入输出格式

输入格式:

每组的第一行有二个正整数(p,k)

p表示字串的行数;

k表示分为k个部分。

接下来的p行,每行均有20个字符。

再接下来有一个正整数s,表示字典中单词个数。(1<=s<=6)

接下来的s行,每行均有一个单词。

输出格式:

一个整数,分别对应每组测试数据的相应结果。

提供一组卡了我好久的数据,注意区间[i,j]的长度。。。

Testdata.in

10 4
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaa
1
aaaaa

Testdata.out

193

比分割字串稍难了一点……主要难在倒推k[i][j] ([i,j]有多少单词),写个模拟就行了吧大概……

 

#洛谷 P1095 守望者的逃离

哇,好像是到目前为止为数不多的几次独立思考并没看题解而写出的dp……

美中不足的是,最后好像忘记初始化状态了……

题目描述

恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会遇难。守望者的跑步速度为17m/s,以这样的速度是无法逃离荒岛的。庆幸的是守望者拥有闪烁法术,可在1s内移动60m,不过每次使用闪烁法术都会消耗魔法值10点。守望者的魔法值恢复的速度为4点/s,只有处在原地休息状态时才能恢复。

现在已知守望者的魔法初值M,他所在的初始位置与岛的出口之间的距离S,岛沉没的时间T。你的任务是写一个程序帮助守望者计算如何在最短的时间内逃离荒岛,若不能逃出,则输出守望者在剩下的时间内能走的最远距离。注意:守望者跑步、闪烁或休息活动均以秒(s)为单位,且每次活动的持续时间为整数秒。距离的单位为米(m)。

输入输出格式

输入格式:

输入文件escape.in仅一行,包括空格隔开的三个非负整数M, S, T。

输出格式:

输出文件escape.out包含两行:

第1行为字符串“Yes”或“No”(区分大小写),即守望者是否能逃离荒岛。

第2行包含一个整数。第一行为“Yes”(区分大小写)时表示守望者逃离荒岛的最短时间;第一行为“No”(区分大小写)时表示守望者能走的最远距离。

我们来看一下,显然要用时间作为状态(因为路程太大而不好转移)而状态必须是二维的(考虑到法术值对决策的影响)

输出了一下sizeof(f[300010][1010])/1024/1024,发现有一个G,怎么办呢?

考虑一个贪心思想,不用白不用啊……

于是就可以设计状态了。我一开始居然想直接f[300010]转移……写着写着发现没法转移。

f[i][j]表示前i秒j个ep最远距离,顺便Notepad++万岁

 

手推一下样例,

exp1
39 200 4
180m 9ep -> 前3s
180m 13ep -> 第4s / 197m 9ep -> 第4s
died.

exp2
36 255 10
180m 6ep -> 前3s
180m 10ep -> 第4s
240m 0ep -> 第5s
257m 0ep -> 第6s

Yes-6s

试着写写方程,写到一半突然相当初始m会很大的问题……于是有了这个……

c1是计数器。

然后试着写写方程,转移一发

为什么要j<=20呢?显然j>10的时候必须直接+17,+60并耗魔法一定不会影响决策……因为不用白不用,用了一定节省时间,所以最优解一定在[0,10)区间里取,f[i][j] (j>=10)再从f[i-1][j+10]转移就没意义了,所以j上限应该是19,手癌就打了个20.

最后别忘记更新一波初始状态,还是注意j<=20

所以这里是全部的代码,注意最后出解j并不影响,所以找到一个直接return 0

但是无解j会影响,显然j<10更优,不用白不用嘛

 

USACO 3.4 “破锣摇滚”乐队 Raucous Rockers

题目描述

你刚刚继承了流行的“破锣摇滚”乐队录制的尚未发表的N(1 <= N <= 20)首歌的版权。你打算从中精选一些歌曲,发行M(1 <= M <= 20)张CD。每一张CD最多可以容纳T(1 <= T <= 20)分钟的音乐,一首歌不能分装在两张CD中。CD数量可以用完,也可以不用完

不巧你是一位古典音乐迷,不懂如何判定这些歌的艺术价值。于是你决定根据以下标准进行选择:

1.歌曲必须按照创作的时间顺序在所有的CD盘上出现。(注:第i张盘的最后一首的创作时间要早于第i+1张盘的第一首)

2.选中的歌曲数目尽可能地多

一开始我看见这道题打了一道背包……

结果很惨的GG了……

我们设f[n][m][k]表示前n首歌按顺序尽量向m张盘里装,然后附加k分钟所能装的最多歌曲数

那么,显然k<=T,因为……如果k>T那f[i][j][k]等价于f[i][j+1][k-T],所以k>T是没有意义的

我们来考虑第n首歌装到第m+1张盘里的决策,也就是转移f[n][m][k] (因为m张盘外加k分钟,如果用那k分钟,也就是向m+1张里面装)

先初始化一下,也就是尝试放弃第i首歌

如果第j+1张盘的前k分钟能装的下,

那就不装,或者用前j张和j+1张的前k-a[i]分钟装前i-1首,第j+1张的最后a[i]分钟(歌曲的长度)装第i首

这两个里面取max

如果第j+1张盘的前k分钟装不下,

那么,假如说存在第j张盘(可以有j=0而k>0,也就是装第一张),那么就不装,或者用前j-1张盘外加第j张盘的T-a[i]分钟装前i-1首,用第j张盘装第i首试一下 (那么,就相当于尽量把第i首歌往j整张盘里装,如果a[i]小于T,那一定能装上,而如果T<a[i]了,那这首歌显然只能放弃)。

我们为什么要有第二个方程?原因在于k不一定大于a[i],而如果这首歌对决策有影响,那么T一定大于a[i],所以有必要试着装一下。

那么整个方程……

然后这是代码……