发现一个物品最多两个附件
于是就四种情况
就是普通背包了
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
// <budget.cpp> - 03/03/16 22:02:32 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; int getint(){ int res=0,fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } #define l(x) a[x][0] #define k(x) a[x][0]*b[x] const int MAXN=61; int n,m; int a[MAXN][3],b[MAXN],c[MAXN]; int dp[MAXN][32001]; void re(int i,int x,int y){ for(int v=n-x;v>=0;v--){ if(!dp[i-1][v])continue; dp[i][v+x]=max(dp[i][v+x],dp[i-1][v]+y); } } int main(){ freopen("budget.in","r",stdin); freopen("budget.out","w",stdout); n=getint();m=getint(); for(int i=1;i<=m;i++){ a[i][0]=getint();b[i]=getint();c[i]=getint(); if(c[i]){ if(a[c[i]][1])a[c[i]][2]=i; else a[c[i]][1]=i; } } dp[0][0]=1; for(int i=1;i<=m;i++){ for(int v=0;v<=n;v++)dp[i][v]=dp[i-1][v]; if(c[i])continue; re(i,l(i),k(i)); if(a[i][1]){ re(i,l(i)+l(a[i][1]),k(i)+k(a[i][1])); if(a[i][2]){ re(i,l(i)+l(a[i][2]),k(i)+k(a[i][2])); re(i,l(i)+l(a[i][1])+l(a[i][2]),k(i)+k(a[i][1])+k(a[i][2])); } } } int ans=0; for(int i=0;i<=n;i++)ans=max(ans,dp[m][i]); printf("%d",ans-1); return 0; } |