题解

1 条题解

  • 0
    @ 2017-03-29 20:34:17
    #include<cstdio>
    #include<ctime>
    using namespace std;
    struct oi
    {
        int a;
        int b;
        int c;
        int num;
    }data[10000];
    int  res[2003][2003];
    int max(int a,int b)
    {
        return a>b;
    }
    int min(int a,int b)
    {
        return a<b;
    }
    int  f[10000][2004];bool can[2003][2003];
    int main()
    {
        freopen("pack.in","r",stdin);
    //  freopen("pack.out","w",stdout);
        int n,m,tot=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {  ++tot;
            scanf("%d",&data[tot].num);
            
            if(data[tot].num==2) 
            {
                
                int x,y,s,t=1;
                
            scanf("%d %d %d",&x,&y,&s);
            
            while(s>=t)
            {
                tot++;
                data[tot].a=x*t;
                data[tot].b=y*t;
                data[tot].num=2;
                s-=t;
                t*=2;
            }
            data[++tot].a=x*s;
            data[tot].b=y*s;
            data[tot].num=2;    
            }
            else if(data[tot].num==3) scanf("%d %d ",&data[tot].a,&data[tot].b);
            else
            {
            scanf("%d %d ",&data[tot].a,&data[tot].b);
                int a=data[tot].a,b=data[tot].b;
                for(int j=1;j<=m;j++)
                {
                    res[tot][j]=j*j*a-b*j;
                }
            }     
        }
        
    
        for(int i=1;i<=tot;i++)
        {
            if(data[i].num==3)
            {
                int money=data[i].a;
                int val=data[i].b;
                for(int j=val;j<=m;j++)
                {
                    f[i][j]=f[i-1][j];
                    int maxd=j/val;
                    for(int k=1;k<=maxd;k++)
                    {
                        //if(j-k*val<0) break;
                        f[i][j]=max(f[i][j],f[i-1][j-k*val]+money*k);
                    }
                    
                }
            }
            if(data[i].num==1)
            {
                for(int j=m;j>=1;j--)
                {
                    int ans=0,a=f[i][j],b;
                    f[i][j]=f[i-1][j];
                    for(int k=1;k<=j;k++)
                    {
                        if(can[j-k][k]==1) continue; 
                    //  v(i,k);
                        if(res[i][k]<0) continue;
                        b=f[i-1][j-k]+res[i][k];
                        if(a<b)
                        {
                            f[i][j]=b;
                            ans=k;
                        }
                    }
                    can[j][ans]=1;
                }
                
            }
            if(data[i].num==2)
            {
                    int money=data[i].a;
                int val=data[i].b;
                
                for(int j=m;j>=val;j--)
                    {   f[i][j]=f[i-1][j];
                        f[i][j]=max(f[i][j],f[i-1][j-val]+money);
                    }
            }   
            
        }
        printf("%d",f[tot][m]);
        printf("\n%.6lf",(double)clock()/CLOCKS_PER_SEC);
        
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    
  • 1

信息

难度
10
分类
(无)
标签
(无)
递交数
1
已通过
0
通过率
0%
上传者