ACACACACACACACWAWAWA(70pt)

P1064 [NOIP2006 提高组] 金明的预算方案

Shabby_fish @ 2019-11-01 20:11:43

求助dalao鸭!!!

背包做的

#include<iostream>
#include<cstdio>
using namespace std;
int zv[64]={},fv[25][2]={},vf[25]={},zp[64]={},fp[25][2]={},nv[25][5]={},np[25][5]={},f[32004]={},n,m;
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
//  freopen("bug.txt","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(c)
        {
            fv[c][vf[c]]=a;
            fp[c][vf[c]++]=b*a;
//          cout<<c<<"-"<<fv[c][vf[c]-1]<<"-"<<fp[c][vf[c]-1]<<endl;
        }
        else
        {
            zv[i]=a;
            zp[i]=b*a;
        }
    }
//  for(int i=1;i<=m;i++)
//    cout<<"v-"<<i<<" "<<zv[i]<<":"<<fv[i][0]<<","<<fv[i][1]<<endl<<"q-"<<i<<" "<<zp[i]<<":"<<fp[i][0]<<","<<fp[i][1]<<endl;
    for(int i=1;i<=m;i++)
    {
        nv[i][1]=zv[i];
        nv[i][2]=zv[i]+fv[i][0];
        nv[i][3]=zv[i]+fv[i][1];
        nv[i][4]=zv[i]+fv[i][1]+fv[i][0];
        np[i][1]=zp[i];
        np[i][2]=zp[i]+fp[i][0];
        np[i][3]=zp[i]+fp[i][1];
        np[i][4]=zp[i]+fp[i][1]+fp[i][0];
//      cout<<"nv["<<i<<"]["<<1<<"]="<<nv[i][1]<<",nv["<<i<<"]["<<2<<"]="<<nv[i][2]<<",nv["<<i<<"]["<<3<<"]="<<nv[i][3]<<",nv["<<i<<"]["<<4<<"]="<<nv[i][4]<<";"<<endl<<"np["<<i<<"]["<<1<<"]="<<np[i][1]<<",np["<<i<<"]["<<2<<"]="<<np[i][2]<<",np["<<i<<"]["<<3<<"]="<<np[i][3]<<",np["<<i<<"]["<<4<<"]="<<np[i][4]<<"."<<endl;
    }
    for(int i=1;i<=m;i++)
      for(int j=n;j>=0;j--)
      {
        if(j>=nv[i][1])     f[j]=max(f[j],f[j-nv[i][1]]+np[i][1]);
        if(j>=nv[i][2])     f[j]=max(f[j],f[j-nv[i][2]]+np[i][2]);
        if(j>=nv[i][3])     f[j]=max(f[j],f[j-nv[i][3]]+np[i][3]);
        if(j>=nv[i][4])     f[j]=max(f[j],f[j-nv[i][4]]+np[i][4]);
//      cout<<"f["<<j<<"]"<<f[j]<<endl;
      }
    cout<<f[n];
    return 0;
}
???

by Shabby_fish @ 2019-11-04 20:59:14

A 了

分享一下原因:数组开小了…


by 㸚茻㠭㗊 @ 2019-11-08 16:11:36

@叕㵘燚㙓 ??


by Shabby_fish @ 2019-11-08 16:28:54

@㸚茻㠭㗊 你不会做还瞎BB


by TonyWu @ 2020-02-18 21:00:54

码辣眼


|