洛谷 p1064 金明的预算方案

这道题以前写过 但没写出来吧

一个普通的01背包 但是有一些物件需要在买过前置物件后才能购买

所以我们用一个vector来存放该背包与其后置的物件 这样写可以做后置物件多于两个的情况 但多于两个时复杂度会很高 O(n!)的复杂度 正解应该是树形背包了就

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;

#define ll long long 
/*ll read()
{
    ll x=0,f=1;
    char c = getchar();
    while(c>'9' || c<'0'){
        if(c=='-') f = -f;
        c = getchar();
    }
    while(c>='0' && c<='9')
    {
        x = x*10+c-'0' ;
        c = getchar();
    }
    return x*f;
}*/
const int maxn = 65;



vector<int> v[maxn];
vector<int> w[maxn];
int dp[33000];
int n,m;

int main()
{
    int v1,v2,q;
    cin >> n >> m;
    int k=1;
    for(int i=1;i<=m;++i)
    {
        cin >> v1>> v2>>q;
        if(q==0)
        {
            v[k].push_back(v1);
            w[k].push_back(v1*v2);
            k++;
        }
        else
        {
            int len =  v[q].size();
            for(int j=0;j<len;++j)
            {
                v[q].push_back(v1+v[q][j]);
                w[q].push_back(v2*v1+w[q][j]);
            } 
        }
    }
    
    for(int i=1;i<k;++i)
    {
        
        for(int s1=n;s1>=v[i][0];s1-=10)    //十的整数倍
        {
            for(int j=0;j<v[i].size();++j)//可以保证当前状态只被该物件及其后置物件转移过一次
            {
                if(s1>=v[i][j])
                    dp[s1] = max(dp[s1],dp[s1-v[i][j]]+w[i][j]);
            }
        }
    }
    cout << dp[n];
    return 0;
}

虽然不难 也有思路但是卡了一些时间 问题在与判断没加等于号
状态转移有问题

洛谷 p1064 金明的预算方案

原文：https://www.cnblogs.com/xxrlz/p/10597423.html