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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

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

你是机器人吗? =。= *