1. T1 拦截导弹

啊,看过无数遍了。。。
显然数据要求$nlogn$。。。
唔,想不起来了。。。
于是开始手动模拟过程,根据脑海中的残留片段,似乎找出了做法,又证明了一下正确性,就AC啦。
LIS的nlogn做法自行百度(CY听到了吗= ̄ω ̄=)

代码:

2. T2 整数划分

啊,写递归被卡常卡成狗啊。
理论上数组开3维还是2维复杂度是一样的。
所以还是写2维的吧

设$f(i,j)$为把前$i$个数字分成$j$段的最大乘积。$sum[i,j]$为第$i$个到第$j$个数字之间的连续数字(如在$n=12345$时,$sum[1,3]=123$)
则:

$f[i][j]=max\{f[k][j-1]×sum[k+1][i]|j-1<=k<i\}$

(语文课推的,草稿在《再别康桥》那里)

每次状态转移记录k的值,输出$f[n][m]$然后递归输出分法。

代码:

3. T3 快餐问题

本来没打算拿分,调其他3题调太久了。
输出平均值拿60分。。。什么鬼。。。

设$f[i][j][k]$为前$i$条流水线,生产$j$个汉堡,$k$个薯条时,最多生产的饮料数。

$f[i][j][k]=max\{f[i][j][k],f[i-1][j-x][k-y]+(t[i]-x×p1-y×p2)/p3\}$

(物理课推的,草稿在《速度快慢变化的描述》那里)
注意有些状态是不能取的,需要判断,比较长,我在状态转移方程里就不写了。
具体看代码。。。

代码:

4. T4 物品装箱问题

一开始我以为我看错问题了,看了好多遍,最后18行1A。

代码: