来自 CY 的礼物

---

T1: 导弹拦截

题意：就是求最长不升子序列和最长下降子序列长度，要求是 O(nlogn) 的算法

看到这题一股气每喘上来，前几天刚看的最长某某序列 nlogn 优化，结果觉得太偏门了，没有学，结果。。。考场上临时脑补出来了。其实我只打了最长下降子序列的算法，对于最长上升子序列，只要对数组每个元素求个相反数即可（把导弹改成潜艇）。

虽然代码很丑，但是还是可以 AC 的

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

#define MX 100001

using namespace std;

int ht[MX+5],have[MX+5],n;

int get1(int num)
{
    int l,r,m,ans;
    l=0,r=n;
    while(l<r)
    {
        m=(l+r+1)/2;
        if(have[m]<num)r=m-1,ans=r;
        else if(have[m]>=num)l=m,ans=l;
    }
    return ans;
}

int get2(int num)
{
    int l,r,m,ans;
    l=0,r=n;
    while(l<r)
    {
        m=(l+r+1)/2;
        if(have[m]<=num)r=m-1,ans=r;
        else l=m,ans=l;
    }
    return ans;
}

int main()
{
    freopen("missile.in","r",stdin);
    freopen("missile.out","w",stdout);
    int pos;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&ht[i]);
    have[0]=99999999;           //求最长不升子序列
    for(int i=1;i<=n;i++)
    {
        pos=get1(ht[i]);
        have[pos+1]=max(have[pos+1],ht[i]);
    }
    for(int i=1;i<=n+1;i++)
        if(have[i]==0)
        {
            cout<<i-1<<endl;
            break;
        }

    for(int i=1;i<=n;i++)have[i]=-MX*10000-1,ht[i]=0-ht[i];
    for(int i=1;i<=n;i++)       //求最长下降子序列（即原数组最长上升子序列）
    {
        pos=get2(ht[i]);
        have[pos+1]=max(have[pos+1],ht[i]);
    }
    for(int i=1;i<=n+1;i++)
        if(have[i]<-MX*10000)
        {
            cout<<i-1<<endl;
            break;
        }
    return 0;
}

---

T2: 整数划分

题意：把一个整数划分为 m 个部分，使这几个部分的乘积最大。

如果 mul[i][j] 表示原数 [i…j] 部分的值，mx[i][j] 表示原数 [1…i] 部分划分 j 次的最大乘积，那么 mx[j][i]=mx[k][i-1]×mul[k+1][j];

一个错误代码：如果遇到有 0 但是要将原数分解为几个一位数乘积的情况会错

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

typedef unsigned long long ull;
int t,m;
int num[20];
ull mul[20][20],now;
ull mx[20][20];
int have[20][20],sep[20];

int main()
{
    freopen("separate.in","r",stdin);
    freopen("separate.out","w",stdout);
    char ch;
    int pos;
    scanf("%d",&t);
    for(int wq=1;wq<=t;wq++)
    {
        pos=0;
        ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
        while(ch>='0'&&ch<='9')
        {
            num[++pos]=ch-'0';
            ch=getchar();
        }
        cin>>m;
        for(int i=1;i<=pos;i++)
        {
            now=0;
            for(int j=i;j<=pos;j++)now=now*10+num[j],mul[i][j]=now;
        }
        memset(mx,0,sizeof(mx));
        memset(have,0,sizeof(have));
        for(int i=1;i<=pos-1;i++)mx[i][1]=mul[1][i];
        for(int i=2;i<=m;i++)
            for(int j=i;j<=pos;j++)
                for(int k=1;k<=j-1;k++)
                    if(mx[k][i-1]*mul[k+1][j]>mx[j][i])mx[j][i]=mx[k][i-1]*mul[k+1][j],have[j][i]=k;
        int nowpos=pos;
        for(int i=m;i>=1;i--)sep[i]=nowpos,nowpos=have[nowpos][i];
        cout<<mx[pos][m]<<endl;
        for(int i=1;i<=m;i++)cout<<mul[sep[i-1]+1][sep[i]]<<" ";
        cout<<endl;
    }
    return 0;
}

更改后的正确代码 (在错误代码的 44 行后添加了一段)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>

using namespace std;

typedef unsigned long long ull;
int t,m;
int num[20];
ull mul[20][20],now;
ull mx[20][20];
int have[20][20],sep[20];

int main()
{
    freopen("separate.in","r",stdin);
    freopen("separate.out","w",stdout);
    char ch;
    int pos;
    scanf("%d",&t);
    for(int wq=1;wq<=t;wq++)
    {
        pos=0;
        ch=getchar();
        while(ch<'0'||ch>'9')ch=getchar();
        while(ch>='0'&&ch<='9')
        {
            num[++pos]=ch-'0';
            ch=getchar();
        }
        cin>>m;
        for(int i=1;i<=pos;i++)
        {
            now=0;
            for(int j=i;j<=pos;j++)now=now*10+num[j],mul[i][j]=now;
        }
        memset(mx,0,sizeof(mx));
        memset(have,0,sizeof(have));
        for(int i=1;i<=pos-1;i++)mx[i][1]=mul[1][i];
        for(int i=2;i<=m;i++)
        {
            for(int j=i;j<=pos;j++)
            {
                for(int k=1;k<=j-1;k++)
                {
                    if(mx[k][i-1]*mul[k+1][j]>mx[j][i])mx[j][i]=mx[k][i-1]*mul[k+1][j],have[j][i]=k;
                    else if(mx[k][i-1]*mul[k+1][j]==mx[j][i])have[j][i]=k;
                }
            }
        }
        int nowpos=pos;
        for(int i=m;i>=1;i--)sep[i]=nowpos,nowpos=have[nowpos][i];
        cout<<mx[pos][m]<<endl;
        for(int i=1;i<=m;i++)cout<<mul[sep[i-1]+1][sep[i]]<<" ";
        cout<<endl;
    }
    return 0;
}

---

T3: 快餐问题

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

这道题我考场上进行骗分，骗到 60 分。事后想想，当初要不是没看完题，其实我可以骗 100 分的

正解：

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 101

using namespace std;

int A,B,C,p1,p2,p3;
int n,t[12];
int col[MX][MX][MX],one[MX][MX][MX];

int main()
{
    freopen("meal.in","r",stdin);
    freopen("meal.out","w",stdout);
    scanf("%d%d%d%d%d%d",&A,&B,&C,&p1,&p2,&p3);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&t[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=100;j++)
            for(int k=1;k<=100;k++)
                if(j*p1+k*p2<=t[i])
                    one[i][j][k]=(t[i]-j*p1-k*p2)/p3;
    memset(col,0xff,sizeof(col));
    col[0][0][0]=0;
    for(int i=1;i<=n;i++)
        for(int p=0;p<=100;p++)
            for(int q=0;q<=100;q++)
                for(int w=0;w<=p&&w*p1<=t[i];w++)
                    for(int e=1;e<=q&&e*p2+w*p1<=t[i];e++)
                        if(col[i-1][p-w][q-e]!=-1)
                            col[i][p][q]=max(col[i][p][q],col[i-1][p-w][q-e]+one[i][w][e]);
    int mx=0;
    for(int i=1;i<=100;i++)
        for(int j=1;j<=100;j++)
            mx=max(mx,min(col[n][i][j]/C,min(i/A,j/B)));
    cout<<mx<<endl;
    return 0;
}

100 分骗分 (无论是考试还是 CodeVS)

#include <iostream>
#include <cstdio>
using namespace std;
int A,B,C,p1,p2,p3,tot,n,t[12];
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);
    for(int i=1;i<=n;i++)scanf("%d",&t[i]),tot+=t[i];
    cout<<min(min(tot/(A*p1+B*p2+C*p3),100/A),min(100/B,100/C))<<endl;
    return 0;
}

---

T4: 物品装箱

题意：有 n 个物品及其替代品，(n<=100), 装到容积为 TOT(TOT<=10000) 的包内，第 i 个物品和其替代品中至多有 1 个装入箱子。每个物品及其替代品都有一个大小和价值，求箱子内物品的最大价值和

水水水，分组背包也不出难点

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>

#define MX 100001

using namespace std;

int w1[MX],w2[MX],v1[MX],v2[MX];
int n,tot,f[MX];

int main()
{
    freopen("box.in","r",stdin);
    freopen("box.out","w",stdout);
    cin>>n>>tot;
    for(int i=1;i<=n;i++)cin>>w1[i]>>v1[i]>>w2[i]>>v2[i];
    for(int i=1;i<=n;i++)
    {
        for(int v=tot;v>=0;v--)
        {
            if(v-w1[i]>=0)f[v]=max(f[v],f[v-w1[i]]+v1[i]);
            if(v-w2[i]>=0)f[v]=max(f[v],f[v-w2[i]]+v2[i]);
        }
    }
    int mx=0;
    for(int i=0;i<=tot;i++)mx=max(mx,f[i]);
    cout<<mx<<endl;
    return 0;
}