70pts 求调!!!

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

Libingyue2011 @ 2023-05-01 09:52:34

#include<bits/stdc++.h>
using namespace std;
int n,m;
int v[110],p[110],q[110];
vector<int>vp[110];
int dp[int(3.2e4)+10],f[int(3.2e4)+10];
int main() {
    cin>>m>>n;//m,n倒着的
    for(int i=1;i<=n;i++)
        cin>>v[i]>>p[i]>>q[i],vp[q[i]].push_back(i),p[i]*=v[i];//将附件搞进vector
    for(int i=1;i<=n;i++){
        if(q[i]!=0) continue;//附件跳过
        for(int j=0;j<=m;j++)//copy上一个状态
            f[j]=dp[j];
        for(int j=m;j>=v[i];j--)//只选这个
            dp[j]=max(f[j],f[j-v[i]]+p[i]);
        if(vp[i].size()==0) continue;//无附件,continue
        if(vp[i].size()>=1)//附件>=1个,只选第一个附件
            for(int j=m;j>=v[i]+v[vp[i][0]];j--)
                dp[j]=max(f[j],f[j-v[i]-v[vp[i][0]]]+p[i]+p[vp[i][0]]);
        if(vp[i].size()==1) continue; //接下来是有两个附件的主场
        for(int j=m;j>=v[i]+v[vp[i][1]];j--)//只选第二个附件
            dp[j]=max(f[j],f[j-v[i]-v[vp[i][1]]]+p[i]+p[vp[i][1]]);
        for(int j=m;j>=v[i]+v[vp[i][0]]+v[vp[i][1]];j--)//两个附件都选
            dp[j]=max(f[j],f[j-v[i]-v[vp[i][0]]-v[vp[i][1]]]+p[i]+p[vp[i][0]]+p[vp[i][1]]);
    }
    cout<<dp[m];
    return 0;
}

by Libingyue2011 @ 2023-05-01 09:53:24

评测记录


by 阿丑 @ 2023-05-08 14:16:14

@Libingyue2011 后面三个 dp[j]=max(f[j],...) 应该改为 dp[j]=max(dp[j],...)


|