感觉是挺不错的一道背包题，题目意思有点依赖背包的感觉（没做过依赖背包），其实可以化简成分组背包（我也没做过），然后再变一变又成01背包了（这个我做过了）。就是感觉自己最近背包特别菜找两道背包来虐虐。
题目：https://www.vijos.org/p/1313
题意：某小明要买东西，需要买价格不超过n，每个物品只买一次，且有一些物品有条件，就是必须买了某个物品才能买那种物品（有点依赖背包的感觉）。现在就问他最大可以买自己认为最值得的值，就是所买物品价格*期望值之和。每个物品的附件不超过两个。
分析一下，买主件的话可以不买附件，但是买附件的话一定要买主件，那我们可不可以把物品划分成：
主件，主件+1号附件，主件+2号附件，主件+1+2号附件。这几种情况（当然他有可能没有两种附件）。
这样分完组，是不是又成了经典的01背包。（orz我当时看成了有很多附件yy了一下2^60的复杂度，选择了重新读一次题）
因为如果不处理好的话，就会发生主件重复购买的事件，所以买东西的时候一定要处理好，为了防止重复买主件，用了滚动数组来记录当前状态，orz写完之后wa了一发，忘记滚动数组状态转移了。。（当然，在处理后面除了单主件的方案数的时候，别忘了跟当前状态对比，因为当前状态已经给更新过了）坑也没多少，就是简单的01背包，换换样。
附上搓搓的代码：
/* @resources: vjios 1313 @date: 2017-4-25 @author: QuanQqqqq @algorithm: dp */
#include <bits/stdc++.h>#define MAXN 33000
#define ll long longusing namespace std;struct node{ll v,p;vector<node> vs;node(ll _v,ll _p) : v(_v),p(_p){}node(){}
}num[65];ll dp[2][MAXN];int main(){ll n,m,v,p,q,tmpv,val;while(~scanf("%lld %lld",&n,&m)){memset(dp,0,sizeof(dp));for(ll i = 1;i <= m;i++){scanf("%lld %lld %lld",&v,&p,&q);if(!q){num[i] = node(v,p);} else {num[q].vs.push_back(node(v,p));num[i] = node(-1,-1);}}ll idx = 0;for(ll i = 1;i <= m;i++){if(num[i].v != -1){ //不是附件 tmpv = num[i].v;val = num[i].v * num[i].p;ll size = num[i].vs.size();for(ll j = n;j >= 0;j--){ //只主件 if(j >= tmpv){dp[idx][j] = max(dp[idx ^ 1][j],dp[idx ^ 1][j - tmpv] + val); } else {dp[idx][j] = dp[idx ^ 1][j];}}for(ll j = 0;j < size;j++){tmpv = num[i].v + num[i].vs[j].v;val = num[i].v * num[i].p + num[i].vs[j].v * num[i].vs[j].p;for(ll k = n;k >= tmpv;k--){dp[idx][k] = max(dp[idx][k],max(dp[idx ^ 1][k],dp[idx ^ 1][k - tmpv] + val));}}if(size == 2){tmpv = num[i].v;val = num[i].v * num[i].p;for(ll j = 0;j < size;j++){ //双附件 tmpv += num[i].vs[j].v;val += num[i].vs[j].v * num[i].vs[j].p;}for(ll j = n;j >= tmpv;j--){ //只主件 dp[idx][j] = max(dp[idx][j],max(dp[idx ^ 1][j],dp[idx ^ 1][j - tmpv] + val));}}idx ^= 1; }}printf("%lld\n",dp[idx ^ 1][n]);}
}
/* 14 5 8 2 0 4 5 1 3 5 1 4 3 0 2 2 0 */