洛谷 P1064 - 金明的预算方案

题目描述

P1064 金明的预算方案

解法：有依赖的背包问题

#include <bits/stdc++.h>using namespace std;const int MAXN = 32005, MAXM = 65;
int v[MAXN][3], p[MAXM][3], f[MAXN];
int n, m, _v, _p, _q;int main()
{
    cin >> n >> m;for(int i=1;i<=m;i++){
    cin >> _v >> _p >> _q;if(!_q){
    v[i][0] = _v;p[i][0] = _p;}else{
    if(v[_q][1]==0){
    v[_q][1] = _v;p[_q][1] = _p;}else{
    v[_q][2] = _v;p[_q][2] = _p;}}}for(int i=1;i<=m;i++){
    auto count_value = [v, p, i](int x){
    return v[i][x]*p[i][x];};auto cost_of_main_annex = [v, p, i](int x, int y){
    return v[i][x]+v[i][y];};auto cost_of_all = [v, p, i](int x, int y, int z){
    return v[i][x]+v[i][y]+v[i][z];};for(int j=n;j>=0;j--){
    if(j>=v[i][0]) // 够买主件f[j] = max(f[j], f[j-v[i][0]]+count_value(0));if(j>=cost_of_main_annex(0, 1)) // 还够买第一个附件f[j] = max(f[j], f[j-cost_of_main_annex(0, 1)]+count_value(0)+count_value(1));if(j>=cost_of_main_annex(0, 2)) // 还够买第二个附件f[j] = max(f[j], f[j-cost_of_main_annex(0, 2)]+count_value(0)+count_value(2));if(j>=cost_of_all(0, 1, 2))f[j] = max(f[j], f[j-cost_of_all(0, 1, 2)]+count_value(0)+count_value(1)+count_value(2));}}cout << f[n] << endl;return 0;
}