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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *