T1

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

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

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m;int a[100005],b[100005],c[100005];
int main()
{
    int i,j,kl;
    n=read();
    for(i=1;i<=n;i++)a[i]=read();
    for(i=n;i>=1;i--){
        kl=upper_bound(b+1,b+1+m,a[i])-b;
        if(kl>m){b[++m]=a[i];}
        else {b[kl]=a[i];}
    }
    printf("%d\n",m);m=0;
    for(i=1;i<=n;i++){
        kl=lower_bound(c+1,c+1+m,a[i])-c;
        if(kl>m){c[++m]=a[i];}
        else {c[kl]=a[i];}
    }
    printf("%d",m);
    return 0;
}

#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 里面答案符合的。
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int m,T;long long n;
unsigned long long f[22][22],a[22][22],s[22];int fa[22][22];
void go(int i,int j){
    if(j==1){printf("%lld ",a[1][i]);return;}
    go(fa[i][j],j-1);printf("%lld ",a[fa[i][j]+1][i]);
}
int main()
{
    int i,j,k,tot=0;
    scanf("%d",&T);
    while(T--){
        scanf("%lld%d",&n,&m);tot=0;
        memset(f,0,sizeof(f));
        while(n){s[++tot]=n%10;n=n/10;}
        for(i=1;i<=tot;i++)a[i][i]=s[tot-i+1];
        for(i=1;i<=tot;i++){
            for(j=i+1;j<=tot;j++)
            a[i][j]=a[i][j-1]*10+a[j][j];
            f[i][1]=a[1][i];
        }
        for(i=1;i<=tot;i++)
            for(j=2;j<=m&&j<=i;j++)
            for(k=j-1;k<i;k++){
                unsigned long long kl=f[k][j-1]*a[k+1][i];
                if(kl>f[i][j]){f[i][j]=kl;fa[i][j]=k;}
        }
        printf("%lld\n",f[tot][m]);
        if(!f[tot][m]){
            for(j=1;j<=m-1;j++)printf("%lld ",a[j][j]);
            printf("%lld\n",a[m][tot]);continue;
        }
        go(tot,m);printf("\n");
    }
    return 0;
}

#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 个饮料是否可行，这肯定得挂吧……
代码：

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int aa,bb,cc,p1,p2,p3,n,ans;
int t[12];
int f[12][102][102];
int main()
{
    int i,j,k,j1,k1,kl;
    scanf("%d%d%d",&aa,&bb,&cc);
    scanf("%d%d%d",&p1,&p2,&p3);
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&t[i]);
    int maxn=min(100/aa,min(100/bb,100/cc));//不超过 100 个，最多生产套餐数
    memset(f,-1,sizeof(f));
    f[0][0][0]=0;
    for(i=1;i<=n;i++)
    for(j=0;j<=maxn*aa;j++)
    for(k=0;k<=maxn*bb;k++)
    for(j1=0;j1<=j;j1++)
    for(k1=0;k1<=k;k1++){
        if(j1*p1+k1*p2>t[i]||f[i-1][j-j1][k-k1]==-1)continue;
        if(f[i][j][k]>=maxn*cc)break;//剪枝
        kl=(t[i]-j1*p1-k1*p2)/p3;
        f[i][j][k]=max(f[i][j][k],f[i-1][j-j1][k-k1]+kl);
    }
    for(j=0;j<=maxn*aa;j++)
        for(k=0;k<=maxn*bb;k++)
        ans=max(ans,min(j/aa,min(k/bb,f[n][j][k]/cc)));
    printf("%d",ans);
    return 0;
}

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

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

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m;
int f[10005];
int aw[105],bw[105],av[105],bv[105];
int main()
{
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        {scanf("%d%d%d%d",&aw[i],&av[i],&bw[i],&bv[i]);}
    for(i=1;i<=n;i++)
        for(j=m;j>=0;j--){
        if(j>=aw[i])f[j]=max(f[j],f[j-aw[i]]+av[i]);
        if(j>=bw[i])f[j]=max(f[j],f[j-bw[i]]+bv[i]);
    }
    printf("%d",f[m]);
    return 0;
}