T1

某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷
达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有
的导弹。
N<=100000

...嗯,水题...
第一问是一个明显的最长不上升子序列,而第二问意会一下就发现是一个最长上升子序列。(因为上升的就是不能接着拦的嘛.)
然后用nlongn的算法搞定即可。
注意一下相同高度的导弹的情况。
话说好久没打过nlongn最长不上升子序列了呢。所以有点虚。

#T2
如何把一个正整数 N(N 长度1)个部分,使这 N 个部分的乘积最
大。N、M 从键盘输入,输出最大值及一种划分方式。
输入数据:
第一行一个正整数 T(T<=10000),表示有 T 组数据。
接下来 T 行每行两个正整数 N,M。

题目还是不难,是一个区间dp。
方程也很好推,每次暴力求出i到j的数a[i][j],然后f[i][j]表示前i个数放j个乘号的结果,则f[i][j]=max(f[k][j-1]*a[k+1][i]);
输出方案可以递归输出,不过要特别注意一下最后答案为0的输出,我就是因为这个丢了40分qwq,解决方案一是特判答案为0的输出方案,这时候的输出方案可以乱输出方案(大雾),解决方案2是递归的时候每次找一遍所有k里面答案符合的。
代码:

#T3
Peter 最近在 R 市开了一家快餐店,为了招揽顾客,该快餐店准备推出一种套餐,该套
餐由 A 个汉堡,B 个薯条和 C 个饮料组成。价格便宜。为了提高产量,Peter 从著名的麦当
劳公司引进了 N 条生产线。所有的生产线都可以生产汉堡,薯条和饮料,由于每条生产线
每天所能提供的生产时间是有限的、不同的,而汉堡,薯条和饮料的单位生产时间又不同。
这使得 Peter 很为难,不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程
序,计算一天中套餐的最大生产量。为简单起见,假设汉堡、薯条和饮料的日产量不超过
100 个。

这个很难....我一开始想了一个和正解有点像,就是代表方案可不可行的算法,复杂度果然不够优化。挂了。
正解是这样的:用f[i][j][k]表示前i台机器生产j个汉堡,k个薯条可以生产的最多饮料数。
则状态转移方程:f[i][j][k]=max(f[i][j][k],f[i-1][j-j1][k-k1]+(p1j1+p2k1)/p3);
但是只是这样还是会超时。
注意到最多生产100个汉堡,薯条和饮料,因此我们可以限定最大套餐可能情况,并且如果f[i][j][k]已经是最大饮料可行数量的话,就能break,不枚举这套j和k了。
然后处理一下每一个f[n][j][k]中生产出的套餐即可。
而我是用f[i][j][k][t]表示前i台机器生产j个汉堡,k个薯条和t个饮料是否可行,这肯定得挂吧......
代码:

#T4
设有 n 种物品,记作 A1、A2、…、An,对应于每个 Ai(1<=i<=n)都有一个重量 Awi
和价值 Avi (重量和价值都为正整数)。另外,对应于每个 Ai,都有一件可代替它的“代用品”Bi,
Bi 的重量和价值分别为 Bwi 和 Bvi。
本题的任务是:选择这 n 件物品或其代用品的一个子集装进背包,使总重量不超过给
定重量 TOT,同时使总价值 VAL 最高。装填的第 I 步,要么装入 Ai,要么装入 Bi,要么 Ai
和 Bi 都不装。

这个是一个裸的分组背包,而且比一般的分组背包还要水一些,因为一个组只有两件物品。
嗯,所以就按照分组背包做就行了。