70分求救

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

gjh303987897 @ 2019-08-16 09:53:40

include<bits/stdc++.h>

using namespace std; int Mv[30001]; int Mc[30001]; int Ov[30001][3]; int Oc[30001][3]; int f[100001]; int n,m,v,p,q; void BEGIN() { freopen("inn.txt","r",stdin); } void END() { int w; freopen("outt.txt","r",stdin); cin>>w; if(w==f[n]) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } cout<<"YOUR :"<<f[n]<<endl; cout<<"ANSERT :"<<w<<endl; } int main() { BEGIN(); cin>>n>>m; for(int i=1;i<=m;i++) { cin>>v>>p>>q; if(!q) { Mv[i]=v;//价格 Mc[i]=vp;//重要度（乘积） }else { Ov[q][0]++; Ov[q][Ov[q][0]]=v; Oc[q][Ov[q][0]]=pv; } } for(int i=1;i<m;i++)//物品 { for(int j=n;j>=Mv[i];j--)//钱数 { f[j]=max(f[j],f[j-Mv[i]]+Mc[i]);//只拿主物品 if(j>=Mv[i]+Ov[i][1])//拿主物品和1号附件（如果有） { f[j]=max(f[j],f[j-Mv[i]-Ov[i][1]]+Mc[i]+Oc[i][1]); } if(j>Mv[i]+Ov[i][2])// 拿主物品和2号附件（如果有） { f[j]=max(f[j],f[j-Mv[i]-Ov[i][2]]+Mc[i]+Oc[i][2]); } if(j>Mv[i]+Ov[i][1]+Ov[i][2])// 拿主物品和1.2号附件（如果有） { f[j]=max(f[j],f[j-Mv[i]-Ov[i][1]-Ov[i][2]]+Mc[i]+Oc[i][2]+Oc[i][1]); } } } // cout<<f[n]; END(); return 0; } 70求救

by Thaumaturge @ 2019-08-16 10:02:19

希望更丰富的展现？使用Markdown

by Thaumaturge @ 2019-08-16 10:04:18

#include<bits/stdc++.h>
using namespace std;
int Mv[30001];
int Mc[30001];
int Ov[30001][3];
int Oc[30001][3];
int f[100001];
int n,m,v,p,q;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>v>>p>>q;
        if(!q)
        {
            Mv[i]=v;//价格 
            Mc[i]=v*p;//重要度（乘积） 
        }else
        {
            Ov[q][0]++;
            Ov[q][Ov[q][0]]=v;
            Oc[q][Ov[q][0]]=p*v;
        }
    }
    for(int i=1;i<m;i++)//物品 
    {
        for(int j=n;j>=Mv[i];j--)//钱数 
        {
            f[j]=max(f[j],f[j-Mv[i]]+Mc[i]);//只拿主物品 
            if(j>=Mv[i]+Ov[i][1])//拿主物品和1号附件（如果有） 
            {
                f[j]=max(f[j],f[j-Mv[i]-Ov[i][1]]+Mc[i]+Oc[i][1]);
            }
            if(j>Mv[i]+Ov[i][2])// 拿主物品和2号附件（如果有）
            {
                f[j]=max(f[j],f[j-Mv[i]-Ov[i][2]]+Mc[i]+Oc[i][2]);
            }
            if(j>Mv[i]+Ov[i][1]+Ov[i][2])// 拿主物品和1.2号附件（如果有）
            {
                f[j]=max(f[j],f[j-Mv[i]-Ov[i][1]-Ov[i][2]]+Mc[i]+Oc[i][2]+Oc[i][1]);
            }
        }
    }
    cout<<f[n];
    return 0;
}

by leoliao @ 2019-08-16 10:04:42

希望更丰富的展现？使用Markdown

by Thaumaturge @ 2019-08-16 10:12:54

第一个错误：分组的转移的j那里要加=号，不然会少判断一些情况（最后一个点因这个WA）

第二个：你物品数那里<m,改成<=m...

~~为什么现在的人总不注意边界呢~~

@gjh303987897

by misaka_八重樱 @ 2019-08-16 10:15:39

望更展，使Md

by gjh303987897 @ 2019-08-16 10:16:35

@misaka_八重樱下次一定用

by xiangling @ 2019-08-17 14:50:00

这题暴力都有70...

by xiangling @ 2019-08-18 17:51:33

我错了

by xiangling @ 2019-08-18 17:51:45

这题暴力80