1. T1 拦截导弹

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

代码：

#include <bits/stdc++.h>
using namespace std;
int n,arr[100005],k[100005],ans;
int main()
{
    freopen("missile.in","r",stdin),freopen("missile.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&arr[i]);
    for(int i=1,j;i<=n;i++)
    {
        j=(int)(upper_bound(k+1,k+1+ans,arr[i],greater<int>())-k);
        ans=max(ans,j);
        if(arr[i]>k[j])k[j]=arr[i];
    }
    printf("%d\n",ans),memset(k,0,sizeof(k)),ans=0;
    for(int i=1,j;i<=n;i++)
    {
        j=(int)(lower_bound(k+1,k+1+ans,arr[i])-k);
        ans=max(ans,j);
        if(arr[i]<k[j]||!k[j])k[j]=arr[i];
    }
    printf("%d\n",ans);
    return 0;
}

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]$然后递归输出分法。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
int t,m,arr[20],len,ans[20][20];
ULL f[20][20],sum[20][20];
int read()
{
    char c=getchar();int cnt=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))arr[++cnt]=c-'0',c=getchar();
    for(int i=1;i<=cnt;i++)sum[i][i]=arr[i];
    for(int i=1;i<=cnt;i++)
        for(int j=i+1;j<=cnt;j++)
            sum[i][j]=sum[i][j-1]*10+arr[j];
    return cnt;
}
void pans(int a,int b)
{
    if(b!=1)pans(ans[a][b],b-1);
    printf("%llu ",sum[ans[a][b]+1][a]);
}
int main()
{
    freopen("separate.in","r",stdin),freopen("separate.out","w",stdout);
    scanf("%d",&t);
    while(t--)
    {
        len=read(),scanf("%d",&m),memset(f,0,sizeof(f));
        for(int i=1;i<=len;i++)f[i][1]=sum[1][i];
        for(int i=2;i<=m;i++)
            for(int j=i;j<=len;j++)
                for(int k=i-1;k<j;k++)
                    if(f[k][i-1]*sum[k+1][j]>=f[j][i])
                    {
                        f[j][i]=f[k][i-1]*sum[k+1][j];
                        ans[j][i]=k;
                    }
        printf("%llu\n",f[len][m]),pans(len,m),printf("\n");
    }
    return 0;
}

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\}$

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

代码：

#include <bits/stdc++.h>
using namespace std;
int a,b,c,p1,p2,p3,n,t[15],f[15][105][105],lim,ans;
int main()
{
    freopen("meal.in","r",stdin),freopen("meal.out","w",stdout);
    scanf("%d%d%d%d%d%d%d",&a,&b,&c,&p1,&p2,&p3,&n);
    lim=min(100/a,min(100/b,100/c)),memset(f,-1,sizeof(f)),f[0][0][0]=0;
    for(int i=1;i<=n;i++)scanf("%d",&t[i]);
    for(int i=1;i<=n;i++)
        for(int j=0;j<=lim*a;j++)
            for(int k=0;k<=lim*b;k++)
                for(int x=0;x<=j;x++)
                    for(int y=0;y<=k;y++)
                        if(t[i]-x*p1-y*p2>=0&&f[i-1][j-x][k-y]!=-1)
                        {
                            f[i][j][k]=max(f[i][j][k],\
                                f[i-1][j-x][k-y]+(t[i]-x*p1-y*p2)/p3);
                            if(f[i][j][k]>lim*c)break;
                        }
    for(int j=0;j<=lim*a;j++)
        for(int k=0;k<=lim*b;k++)
            ans=max(ans,min(j/a,min(k/b,f[n][j][k]/c)));
    printf("%d\n",ans);
    return 0;
}

4. T4 物品装箱问题

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

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m,w1[105],v1[105],w2[105],v2[105],f[10005];
int main()
{
    freopen("box.in","r",stdin),freopen("box.out","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&w1[i],&v1[i],&w2[i],&v2[i]);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=min(w1[i],w2[i]);j--)
        {
            if(j>=w1[i])f[j]=max(f[j],f[j-w1[i]]+v1[i]);
            if(j>=w2[i])f[j]=max(f[j],f[j-w2[i]]+v2[i]);
        }
    printf("%lld\n",f[m]);
    return 0;
}