- 金明的预算方案
- 2016-10-13 20:23:01 @
RT 只过了两个点
```c++
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
inline int max(int a,int b){
return (a>b)?a:b;
}
class addon{
public:
int p;
int v;
addon(){
}
addon(int _p,int _v):p(_p),v(_v){
}
int value(){
return p * v;
}
};
class primary :public addon{
public:
vector<addon> addons;
primary(){
}
primary(int _p,int _v){
p = _p;
v = _v;
}
};
primary *p;
long dp[32001] = {0};
int n,m;
int main(int argc,char ** argv){
int pi,vi,ii,id = 0;
cin>>n>>m;
p = new primary[m];
for(int x=0;x!=m;x++){
cin>>pi>>vi>>ii;
if(!ii){
p[id++] = primary(pi,vi);
}else{
p[--ii].addons.push_back(addon(pi,vi));
}
}
for(int x=0;x!=id;x++){
for(int y=n;y>=p[x].p;y--){
dp[y] = max(dp[y],dp[y-p[x].p] + p[x].value() );
if(p[x].addons.size()>=1){
if(p[x].addons[0].p + p[x].p <= y){
dp[y] = max(dp[y],dp[y-p[x].p-p[x].addons[0].p] + p[x].value() + p[x].addons[0].value() );
}
if(p[x].addons.size()>=2){
if(p[x].addons[1].p + p[x].p <= y){
dp[y] = max(dp[y],dp[y-p[x].p-p[x].addons[1].p] + p[x].value() + p[x].addons[1].value() );
}
if(p[x].addons[0].p + p[x].addons[1].p + p[x].p <= y){
dp[y] = max(dp[y],dp[y-p[x].p-p[x].addons[0].p-p[x].addons[1].p] + p[x].value() + p[x].addons[0].value() + p[x].addons[1].value());
}
}
}
}
}
cout<<dp[n]<<endl;
return 0;
}
```