钦定与暴力与dp
```c++
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n, m;
int v[100], p[100], q[100];

struct p {
int to, next;
}edge[100];
int head[100], top = 0;
int dp[32005];

void push(int i, int j)
{
edge[++top].to = j;
edge[top].next = head[i];
head[i] = top;
}

int main()
{
scanf("%d%d", &n, &m);
n /= 10;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &v[i], &p[i], &q[i]);
v[i] /= 10;
if (q[i])
push(q[i], i);
}
memset(dp, 0, sizeof dp);
for (int i = 1; i <= m; i++){
for (int j = n; j >= v[i]; j--) if (!q[i]){
int pst = dp[j];
//if (dp[j-v[i]]+p[i]*v[i] >= dp[j]) {
dp[j] = dp[j-v[i]]+p[i]*v[i];
int choice[4], tp = 0;
for (int k = head[i]; k; k = edge[k].next)
choice[++tp] = edge[k].to;
if (tp >= 1 && j-v[i]-v[choice[1]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[1]]]+p[i]*v[i]+p[choice[1]]*v[choice[1]]);
if (tp >= 2) {
if (j-v[i]-v[choice[2]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[2]]]+p[i]*v[i]+p[choice[2]]*v[choice[2]]);
if (j-v[i]-v[choice[1]]-v[choice[2]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[1]]-v[choice[2]]]+p[i]*v[i]+p[choice[1]]*v[choice[1]]+p[choice[2]]*v[choice[2]]);
}
if (tp >= 3) {
if (j-v[i]-v[choice[3]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]]+p[i]*v[i]+p[choice[3]]*v[choice[3]]);
if (j-v[i]-v[choice[3]]-v[choice[2]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]-v[choice[2]]]+p[i]*v[i]+p[choice[3]]*v[choice[3]]+p[choice[2]]*v[choice[2]]);
if (j-v[i]-v[choice[3]]-v[choice[1]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]-v[choice[1]]]+p[i]*v[i]+p[choice[3]]*v[choice[3]]+p[choice[1]]*v[choice[1]]);
if (j-v[i]-v[choice[3]]-v[choice[2]]-v[choice[1]] >= 0)
dp[j] = max(dp[j], dp[j-v[i]-v[choice[3]]-v[choice[2]]-v[choice[1]]]+p[i]*v[i]+p[choice[1]]*v[choice[1]]+p[choice[3]]*v[choice[3]]+p[choice[2]]*v[choice[2]]);
}
//}
dp[j] = max(pst, dp[j]);
}
}

cout << dp[n]*10 <<endl;
return 0;
}
```

#include<iostream>//c++
#include<cmath>//数学公式
#include<cstdlib>//malloc
#include<cstring>
#include<string>
#include<cstdio>//输入输出
#include<algorithm>//快排
#include<queue>//队列
#include<functional>//优先队列
#include<stack>//栈
#include<vector>//容器
#include<map>//地图 if continue
typedef long long ll;
const int N=30+3200;
using namespace std;
typedef struct
{
int v,p,q,c;
}G;G g[66];
//int w[N][N];
int dp[N];
//char c[N];
//map<string,int>map;
//vector<int>v;
//stack<int>s;
//queue<int> q;
//priority_queue<int> q;//大到小
//priority_queue<int, vector<int>,greater<int> >q;//小到大
int main()
{
//freopen("C:\Users\ch\Desktop\1.txt","r",stdin);
//freopen("C:\Users\lenovo\Desktop\2.txt","w",stdout);
int i,j,a,b;
int m,n,x,y;
memset(g,0,sizeof(g));
while(~scanf("%d%d",&m,&n))
{
for(i=1;i<=n;i++) cin>>g[i].v>>g[i].p>>g[i].q,g[i].v/=10,g[i].c=g[i].p*g[i].v;
m/=10;
for(i=1;i<=n;i++)
if(g[i].q==0)
{
for(j=2;j<=n;j++) if(g[j].q==i) break; a=g[j].c;int a1=g[j].v;//cout<<i<<"a "<<a<<endl;
for(j++;j<=n;j++) if(g[j].q==i) break; b=g[j].c;int b1=g[j].v;//cout<<i<<"b "<<b<<endl;
for(j=m;j>=g[i].v;j--)
{
dp[j]=max(dp[j],dp[ j-g[i].v ]+g[i].c);//主件
x=g[i].v+a1; y=g[i].c+a;
if(x<=j) dp[j]=max(dp[j],dp[j-x]+y);//主件+附件1
x=g[i].v+b1; y=g[i].c+b;
if(x<=j) dp[j]=max(dp[j],dp[j-x]+y);//主件+附件2
x=g[i].v+a1+b1; y=g[i].c+a+b;
if(x<=j) dp[j]=max(dp[j],dp[j-x]+y);//主件+附件2+附件3

}
}
cout<<dp[m]*10<<endl;
//for(i=0;i<100;i++)cout<<dp[i]<<endl;
}
return 0;
}

内存 500 KB 秒杀
可以通过调整循环次序把数组压缩成一维
又因为所有价格都为10的倍数，故可以把价格全部除以10，预算也除以10，背包完了后再把答案乘以10
所以总的时间复杂度降为原来的1/10，空间复杂度降为原来的约1/100

#include <stdio.h>

int numThing[100];
int costs[100][5];
int values[100][5];

int dp[3201];

int MAX(int a, int b){
return a>b ? a:b;
}
int main(){
int limit, num;
int cost, value, index, i, k;

scanf("%d %d", &limit, &num);
limit /= 10;
for(i=0; i<=num; i++)
numThing[i] = 0;
for(i=0; i<num; i++){
scanf("%d %d %d", &cost, &value, &index);
index--;
if(index < 0)
index = i;
costs[index][numThing[index]] = cost/10;
values[index][numThing[index]] = value;
numThing[index]++;
}

for(i=0; i<=limit; i++)
dp[i] = 0;

for(i=0; i<num; i++){
if(numThing[i] == 0)
continue;
for(k=limit; k>=costs[i][0]; k--){
switch(numThing[i]){
case 3:
if(k-costs[i][0]-costs[i][1]-costs[i][2] >= 0)
dp[k] = MAX(dp[k], dp[k-costs[i][0]-costs[i][1]-costs[i][2]] + values[i][0]*costs[i][0] + values[i][1]*costs[i][1] + values[i][2]*costs[i][2]);
case 2:
if(k-costs[i][0]-costs[i][1] >= 0)
dp[k] = MAX(dp[k], dp[k-costs[i][0]-costs[i][1]] + values[i][0]*costs[i][0] + values[i][1]*costs[i][1]);
if(k-costs[i][0]-costs[i][2] >= 0)
dp[k] = MAX(dp[k], dp[k-costs[i][0]-costs[i][2]] + values[i][0]*costs[i][0] + values[i][2]*costs[i][2]);
case 1:
dp[k] = MAX(dp[k], dp[k-costs[i][0]] + values[i][0]*costs[i][0]);
}
}
}
printf("%d\n", dp[limit]*10);

return 0;
}

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<fstream>
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int N,M;
struct node{
int v,p,q,c;
}th[100];
int f[100][32001];//f[i][j]第i组的附件组成价值为j的最优解
int a[100][100];
int root[100];
int tot;//总组数
int ans[32001];
int main(){
N=read(); M=read();
for(int i=1;i<=M;i++){
th[i].v=read(); th[i].p=read(); th[i].q=read();
th[i].c=th[i].p*th[i].v;//计算出物品的价值
}
for(int i=1;i<=M;i++){
if(th[i].q!=0){
int now=th[i].q;//所属的主件物品编号
int tmp=++a[now][0];//主件的附件个数
a[now][tmp]=i;
}
else{
tot++;//主件个数加一
root[tot]=i;
}
}
//01背包
for(int i=1;i<=tot;i++){//枚举主件
int zhu=root[i];
for(int j=1;j<=a[zhu][0];j++){//枚举该主件的附件
for(int v=N;v>=0;v--){//钱
int temp=a[zhu][j];
int jian=th[temp].v;
int jia=th[temp].c;
if(v>=jian){
f[zhu][v]=max(f[zhu][v],f[zhu][v-jian]+jia);
}
}
}
}
//分组背包
for(int i=1;i<=tot;i++){
int zhu=root[i];
for(int v=N;v>=0;v--){
for(int k=0;k<=N;k++){
if(v-k-th[zhu].v>=0){
ans[v]=max(ans[v],ans[v-k-th[zhu].v]+f[zhu][k]+th[zhu].c);
}
}
}
}
cout<<ans[N];
return 0;
}

/*

author: Slience_K
Belong: C++
Pro: LGOJ P 1064

*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n , m , tot , v[ 65 ][ 3 ] , w[ 65 ][ 3 ] , order[ 65 ];
int f[ 32005 ] , num[ 65 ] , x , y , z;
int main(){
freopen( "P1064.in" , "r" , stdin );
scanf( "%d%d" , &n , &m );
for( int i = 1 ; i <= m ; i++ ){
scanf( "%d%d%d" , &x , &y , &z );
if ( z == 0 ){
tot++;
order[ i ] = tot;
v[ tot ][ 0 ] = x;
w[ tot ][ 0 ] = x * y;
}
else{
num[ order[ z ] ]++;
v[ order[ z ] ][ num[ order[ z ] ] ] = x;
w[ order[ z ] ][ num[ order[ z ] ] ] = x * y;
}
}
f[ 0 ] = 1;
for( int i = 1 ; i <= tot ; i++ )
for( int j = n ; j >= 0 ; j-- ){
if (( j - v[ i ][ 0 ] >= 0 )&&( f[ j - v[ i ][ 0 ] ] ))
f[ j ] = max( f[ j ] , f[ j - v[ i ][ 0 ] ] + w[ i ][ 0 ] );
if (( j - v[ i ][ 0 ] - v[ i ][ 1 ] >= 0 )&&
( f[ j - v[ i ][ 0 ] - v[ i ][ 1 ] ] ))
f[ j ] = max( f[ j ] , f[ j - v[ i ][ 0 ] - v[ i ][ 1 ] ] + w[ i ][ 0 ] + w[ i ][ 1 ] );
if (( j - v[ i ][ 0 ] - v[ i ][ 2 ] >= 0 )&&
( f[ j - v[ i ][ 0 ] - v[ i ][ 2 ] ] ))
f[ j ] = max( f[ j ] , f[ j - v[ i ][ 0 ] - v[ i ][ 2 ] ] + w[ i ][ 0 ] + w[ i ][ 2 ] );
if (( j - v[ i ][ 0 ] - v[ i ][ 1 ] - v[ i ][ 2 ] >= 0 )&&
( f[ j - v[ i ][ 0 ] - v[ i ][ 1 ] - v[ i ][ 2 ] ] ))
f[ j ] = max( f[ j ] ,
f[ j - v[ i ][ 0 ] - v[ i ][ 1 ] - v[ i ][ 2 ] ] + w[ i ][ 0 ] + w[ i ][ 1 ] + w[ i ][ 2 ] );
}
int maxn = 0;
for( int i = 0 ; i <= n ; i++ )
maxn = max( maxn , f[ i ] );
printf( "%d" , maxn - 1 );
return 0;
}

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 292 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 292 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 292 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 288 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 292 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 292 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 288 KiB, score = 10
Accepted, time = 0 ms, mem = 292 KiB, score = 100

http://www.cnblogs.com/oierforever/p/4764097.html

明明最多就两个附件，直接dp+枚举即可，不需要分组，遇到子物品跳过
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
int v[61],w[61],q[61];
int f[62][32010];
vector<int> sub[61];
int n,m;
int dp(int i,int j)
{
if(f[i][j]!=-1)
return f[i][j];
if(i>m)
{
f[i][j]=0;
return f[i][j];
}
if(q[i]!=0)
{
f[i][j]=dp(i+1,j);
return f[i][j];
}
if(v[i]<=j)
{
if(sub[i].size()==0)
f[i][j]=dp(i+1,j-v[i])+v[i]*w[i];
else if(sub[i].size()==1)
{
if(v[i]+v[sub[i][0]]<=j)
f[i][j]=dp(i+1,j-v[i]-v[sub[i][0]])+v[i]*w[i]+v[sub[i][0]]*w[sub[i][0]];
f[i][j]=max(f[i][j],dp(i+1,j-v[i])+v[i]*w[i]);
}
else
{
if(v[i]+v[sub[i][0]]+v[sub[i][1]]<=j)
f[i][j]=dp(i+1,j-v[i]-v[sub[i][0]]-v[sub[i][1]])+v[i]*w[i]+v[sub[i][0]]*w[sub[i][0]]+v[sub[i][1]]*w[sub[i][1]];
if(v[i]+v[sub[i][0]]<=j)
f[i][j]=max(f[i][j],dp(i+1,j-v[i]-v[sub[i][0]])+v[i]*w[i]+v[sub[i][0]]*w[sub[i][0]]);
if(v[i]+v[sub[i][1]]<=j)
f[i][j]=max(f[i][j],dp(i+1,j-v[i]-v[sub[i][1]])+v[i]*w[i]+v[sub[i][1]]*w[sub[i][1]]);
f[i][j]=max(f[i][j],dp(i+1,j-v[i])+v[i]*w[i]);

}
}
f[i][j]=max(f[i][j],dp(i+1,j));
return f[i][j];
}
int main()
{
scanf("%d%d",&n,&m);
memset(f,-1,sizeof(f));
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v[i],&w[i],&q[i]);
if(q[i]!=0)
sub[q[i]].push_back(i);
}
printf("%d\n",dp(1,n));
return 0;
}

var
n,m:longint;
newv,newp:array[-1000..maxint] of longint;
v,p,q:array[-1000..maxint] of longint;
f:array[-1000..maxint] of longint;
function calc(k:longint):longint;
var
i,j,x:longint;
begin
x:=1;
newv[1]:=v[k];
newp[1]:=p[k];
for i:=1 to m do
if q[i]=k then
begin
for j:=1 to x do
begin
newv[j+x]:=newv[j]+v[i];
newp[j+x]:=newp[j]+p[i];
end;
x:=x*2;
end;
exit(x);
end;
procedure dp;
var
i,j,k,temp:longint;
begin
fillchar(f,sizeof(f),0);
for i:=1 to m do
begin
if q[i]<>0 then continue;
for j:=n downto 1 do
for k:=1 to calc(i) do
if j>=newv[k] then
if (f[j]<f[j-newv[k]]+newp[k]) then f[j]:=f[j-newv[k]]+newp[k];
end;
end;
procedure init;
var
i:longint;
begin
read(n,m);
for i:=1 to m do
begin
read(v[i],p[i],q[i]);
p[i]:=p[i]*v[i];
end;
end;
begin
init;
dp;
writeln(f[n]);
end.

记录信息

评测状态 Accepted
题目 P1313 金明的预算方案
递交时间 2014-09-28 21:33:29
代码语言 C++
评测机 VijosEx
消耗时间 60 ms
消耗内存 8048 KiB
评测时间 2014-09-28 21:33:33

评测结果

编译成功

foo.cpp: In function 'int main()':
foo.cpp:49:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wparentheses]
if( q[i] != 0 )
^

测试数据 #0: Accepted, time = 15 ms, mem = 8048 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 8044 KiB, score = 10

测试数据 #2: Accepted, time = 0 ms, mem = 8044 KiB, score = 10

测试数据 #3: Accepted, time = 0 ms, mem = 8048 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 8048 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 8044 KiB, score = 10

测试数据 #6: Accepted, time = 0 ms, mem = 8044 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 8048 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 8044 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 8048 KiB, score = 10

Accepted, time = 60 ms, mem = 8048 KiB, score = 100

代码

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int n , m;
int i;
int v[60 + 2][3];
int p[60 + 2][3];
int q[60 + 2];
int ftc[32000 + 2][60 + 2];

int maxd( int a , int b , int c , int d , int e )
{
return max( max( a , b ) , max( max( c , d ) , e ) );
}

int f( int a , int b )
{
//cout << a << " " << b << endl;
if( a < 0 )
return -1000000000;
if( b > m )
return -1000000000;
if( a == 0 )
return 0;
if( b == m )
return 0;
if( v[b][0] == -100 )
{
if( ftc[a][b] == 0 )
ftc[a][b] = f( a , b + 1 );
return ftc[a][b];
}
if( ftc[a][b] == 0 )
ftc[a][b] = maxd( f( a , b + 1 ) , f( a - v[b][0] , b + 1 ) + v[b][0] * p[b][0] , f( a - v[b][0] - v[b][1] , b + 1 ) + v[b][0] * p[b][0] + v[b][1] * p[b][1] , f( a - v[b][0] - v[b][2] , b + 1 ) + v[b][0] * p[b][0] + v[b][2] * p[b][2] , f( a - v[b][0] - v[b][1] - v[b][2] , b + 1 ) + v[b][0] * p[b][0] + v[b][1] * p[b][1] + v[b][2] * p[b][2] );
return ftc[a][b];
}

int main()
{
while( scanf( "%d %d" , &n , &m ) != EOF )
{
for( i = 0 ; i < m ; i++ )
scanf( "%d %d %d" , &v[i][0] , &p[i][0] , &q[i] );
for( i = 0 ; i < m ; i++ )
if( q[i] != 0 )
if( v[ q[i] - 1 ][1] == 0 )
{
v[ q[i] - 1 ][1] = v[i][0];
p[ q[i] - 1 ][1] = p[i][0];
v[i][0] = -100;
p[i][0] = -100;
}
else
{
v[ q[i] - 1 ][2] = v[i][0];
p[ q[i] - 1 ][2] = p[i][0];
v[i][0] = -100;
p[i][0] = -100;
}
cout << f( n , 0 ) << endl;
}
return 0;
}

简单dp

测试数据 #0: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 764 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 772 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 768 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 768 KiB, score = 10
Accepted, time = 0 ms, mem = 772 KiB, score = 100
代码
var
v,w,q:array[0..60]of longint;
s:array[1..60,0..2]of longint;
f,f1:array[0..3200]of longint;
i,j,n,m,x,y:longint;
begin
read(n,m); n:=n div 10;
for i:=1 to m do
begin
read(v[i],w[i],q[i]);
v[i]:=v[i] div 10;
w[i]:=v[i]*w[i];
if q[i]>0 then
begin
inc(s[q[i],0]);
s[q[i],s[q[i],0]]:=i;
end;
end;
for i:=1 to m do
if q[i]=0 then
begin
x:=v[i]; f1:=f;
for j:=n downto x do
if f1[j-x]+w[i]>f[j] then
f[j]:=f[j-x]+w[i];
if s[i,0]=1 then
begin
inc(x,v[s[i,1]]);
for j:=n downto x do
if f1[j-x]+w[i]+w[s[i,1]]>f[j] then
f[j]:=f1[j-x]+w[i]+w[s[i,1]];
end;
if s[i,0]=2 then
begin
inc(x,v[s[i,1]]);
for j:=n downto x do
if f1[j-x]+w[i]+w[s[i,1]]>f[j] then
f[j]:=f1[j-x]+w[i]+w[s[i,1]];
inc(x,v[s[i,2]]);
for j:=n downto x do
if f1[j-x]+w[i]+w[s[i,1]]+w[s[i,2]]>f[j] then
f[j]:=f1[j-x]+w[i]+w[s[i,1]]+w[s[i,2]];
dec(x,v[s[i,1]]);
for j:=n downto x do
if f1[j-x]+w[i]+w[s[i,2]]>f[j] then
f[j]:=f1[j-x]+w[i]+w[s[i,2]];
end;
end;
write(f[n]*10);
end.

评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 452 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 452 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 452 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 452 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 452 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 444 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 444 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 444 KiB, score = 10
Accepted, time = 15 ms, mem = 452 KiB, score = 100
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct item
{
int v[4], w[4], c;
} a[65];
int ind[65];
int main()
{
int n, m, j;
scanf("%d%d", &n, &m);
j = 1;
n /= 10;

for(int i = 1; i <= m; i++)
{
int v, p, q;
scanf("%d%d%d", &v, &p, &q);
v /= 10;

if(q == 0)
{
a[j].v[0] = v;
a[j].w[0] = p * v;
a[j].c = 1;
ind[i] = j;
j++;
}
else
{
q = ind[q];

if(a[q].c == 1)
{
a[q].v[1] = a[q].v[0] + v;
a[q].w[1] = a[q].w[0] + v * p;
a[q].c = 2;
}
else if(a[q].c == 2)
{
a[q].v[2] = a[q].v[0] + v;
a[q].w[2] = a[q].w[0] + v * p;
a[q].v[3] = a[q].v[1] + v;
a[q].w[3] = a[q].w[1] + v * p;
a[q].c = 4;
}
}
}

int dp[3500] = {0};

for(int i = 1; i < j; i++)
for(int k = n; k > 0; k--)
for(int x = 0; x < a[i].c; x++)
if(k >= a[i].v[x])
dp[k] = max(dp[k], dp[k - a[i].v[x]] + a[i].w[x]);

printf("%d\n", dp[n] * 10);
return 0;
}

测试数据 #0: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 872 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 872 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 872 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 868 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 868 KiB, score = 10
Accepted, time = 15 ms, mem = 872 KiB, score = 100

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct item{
int v[4], w[4], c;
}a[65];
int ind[65];
int main()
{ int n, m, j;
scanf("%d%d", &n, &m);
j = 1;
n /= 10;
for (int i = 1; i <= m; i++)
{ int v, p, q;
scanf("%d%d%d", &v, &p, &q);
v /= 10;
if (q == 0)
{ a[j].v[0] = v;
a[j].w[0] = p*v;
a[j].c = 1;
ind[i] = j;
j++;
}
else
{ q = ind[q];
if (a[q].c == 1)
{ a[q].v[1] = a[q].v[0] + v;
a[q].w[1] = a[q].w[0] + v*p;
a[q].c = 2;
}
else if (a[q].c == 2)
{ a[q].v[2] = a[q].v[0] + v;
a[q].w[2] = a[q].w[0] + v*p;
a[q].v[3] = a[q].v[1] + v;
a[q].w[3] = a[q].w[1] + v*p;
a[q].c = 4;
}
}
}
int dp[3500] = {0};
for (int i = 1; i < j; i++)
for (int k = n; k > 0; k--)
for (int x = 0; x < a[i].c; x++)
if ( k >= a[i].v[x])
dp[k] = max(dp[k], dp[k-a[i].v[x]]+a[i].w[x]);
printf("%d\n",dp[n]*10);
return 0;
}
好不爽，被主件編號坑了

var x,y,i,j,ans,n,m:longint;
v,w,p,q1,q2:array[0..61] of longint;
f:array[0..32001] of longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
procedure start;
begin
fillchar(v,sizeof(v),0);
fillchar(w,sizeof(w),0);
fillchar(p,sizeof(p),0);
fillchar(q1,sizeof(q1),0);
fillchar(q2,sizeof(q2),0);
readln(n,m);
for i:=1 to m do
begin
readln(v[i],w[i],p[i]);
w[i]:=v[i]*w[i];
q2[p[i]]:=q1[p[i]];
q1[p[i]]:=i;
end;
end;
procedure main;
begin
fillchar(f,sizeof(f),0);
f[0]:=1;
for i:=1 to m do
if p[i]=0 then
for j:=n downto 0 do
begin
if (j-v[i]>=0) and (f[j-v[i]]<>0) then f[j]:=max(f[j],f[j-v[i]]+w[i]);
x:=v[i]+v[q1[i]];y:=w[i]+w[q1[i]];
if (j-x>=0) and (f[j-x]<>0) then f[j]:=max(f[j],f[j-x]+y);
x:=x+v[q2[i]];y:=y+w[q2[i]];
if (j-x>=0) and (f[j-x]<>0) then f[j]:=max(f[j],f[j-x]+y);
x:=x-v[q1[i]];y:=y-w[q1[i]];
if (j-x>=0) and (f[j-x]<>0) then f[j]:=max(f[j],f[j-x]+y);
end;
end;
procedure print;
begin
ans:=f[n];
for i:=n-1 downto 0 do if f[i]>ans then ans:=f[i];
writeln(ans-1);
end;
begin
start;
main;
print;
end.

var i,j,k,n,m:longint;
x,y:int64;
v:array[0..201,0..2001] of int64;
f:array[0..2001] of int64;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y);
for j:=1 to n do
begin
v[i,j]:=x;
for k:=1 to y do v[i,j]:=v[i,j]*j;
end;
end;
f[0]:=0;
for i:=1 to n do f[i]:=maxlongint;
for k:=1 to m do
for i:=n-1 downto 0 do
for j:=1 to n-i do
if (f[i]+v[k,j]<f[i+j]) then f[i+j]:=f[i]+v[k,j];
writeln(f[n]);
end.

终于AC了

Vijos 题解：http://hi.baidu.com/umule/item/2c997f8ed9600fdae596e017
有疑问请留言 共同进步

金明的预算方案
如果看过普及组试卷就会发现，对应的第二个题目，也是一个样的背景，提高组只是多了个“主件附件”的的关系，如果去掉这一点，就全没区别了。也就成了经典的背包问题了。也就是多了这么一点，考试的时候就晕了。不知道怎么做了。后来才发现是个很简单的dp题目。可惜我当时没做出来。
草率的审题，可能会得到这样的算法：dp，对每一个物品做两种决策，取与不取。如果取，满足两个条件：1.要么它是主件，要么它所属的主件已经在包里了。2.放进去后的重要度与价格的成绩的总和要比没放进时的大。这两个条件缺一不可的。于是呼，得到如下的动规方程：
f[i,j]:=f[i-1,j];
if (i为主件or i的附件在包中）and (f[i,j]<f[i,j-v]+v*w)
then f[i,j]:=f[i,j-v]+v*w;
我们来分析一下复杂度，空间：dp的阶段为n^2,对与每一个阶段都要记录该状态下在包中的物品有哪些（因为要确定附件的主件是否在包中)，每个阶段的记录都要O(n)的空间，所以总的就是O(n^3)。时间，一个dp，n^2的外层循环，内部用布尔量加个主附件的对应数组，为O(1)，和起来就为O(n^2)的复杂度。
可以看的出，时间的需求为32000*60，不成问题。空间32000*60*60，大约要7.5M的空间，在64M的要求下是完全可以的过的。如果用上题目中的一个很隐秘的条件：“每件物品都是10元的整数倍”，就可以把速度在提高十倍。
细细的看题目，还一个很重要的条件我们还没用：“每个主件可以有0个，1个或2个附件”。这貌似不起眼的一句话，却给我们降低复杂度提供了条件。想一想，为什么题目要对附件的个数做限制呢，明显是在降低难度。
对于一套物品（包含主件，所以的附件），我们称为一个属类，对一个属类的物品的购买方法，有以下5种：
1.一个都不买
2.主件
3.主件＋附件1
4.主件＋附件2
5.主件＋附件1＋附件2
这五种购买方法也是唯一的五种方法，也就是说对一属类的物品，我们只有上述的5种购买方法。
于是我们很自然的就会想到把物品按物品的属类捆在一起考虑。这样我们把物品的属类作为dp的状态。可以得到如下的dp方程：
f[i,j]=max{f[i-1,j];
f[i-1,j-v[i,0]]+v[i,0]*w[i,0];
f[i-1,j-v[i,0]-v[i,1]]+v[i,0]*w[i,0]+v[i,1]*w[i,1];
f[i-1,j-v[i,0]-v[i,2]]+v[i,0]*w[i,0]+v[i,2]*w[i,2];
f[i-1,j-v[i,0]-v[i,1]-v[i,2]]+v[i,0]*w[i,0]+v[i,1]*w[i,1]+v[i,2]*w[i,2];}
很显然时间复杂度为O(n^2)，空间复杂度为O(n^2)，加上利用“每件物品都是10元的整数倍”除以10的优化，本题就很完美的解决了。
（附程序）；

program Qi(input,output);
type
node=record
u:integer;
v:array[0..2] of integer;
p:array[0..2] of integer;
end;
var
n,m,k:integer;
w:array[1..60] of node;
f:array[0..60,0..3200] of longint;
g:array[1..60] of integer;
procedure init;
var
i,j:integer;
vx,px,qx:array[1..60] of integer;
begin
readln(n,m); k:=0;
for i:=1 to m do
begin
readln(vx,px,qx);
if qx=0
then begin
k:=k+1; g:=k;
with w[k] do
begin
u:=0;
v[0]:=vx; p[0]:=px;
for j:=1 to 2 do begin v[j]:=0; p[j]:=0; end;
end;
end;
end;
for i:=1 to m do
if qx<>0
then begin
with w[g[qx]] do
begin
u:=u+1;
v:=vx; p:=px;
end;
end;
for i:=1 to k do
with w do
begin
for j:=0 to 2 do write('(',v[j],',',p[j],') ');
writeln;
end;
end;
procedure doit;
var
i,j:integer;
begin
fillchar(f,sizeof(f),0);
for i:=1 to k do
with w do
begin
for j:=1 to n do
begin
f[i,j]:=f[i-1,j];
if (j>=v[0]) and (f[i,j]<f[i-1,j-v[0]]+v[0]*p[0])
then f[i,j]:=f[i-1,j-v[0]]+v[0]*p[0];
if (j>=v[0]+v[1]) and (f[i,j]<f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1])
then f[i,j]:=f[i-1,j-v[0]-v[1]]+v[0]*p[0]+v[1]*p[1];
if (j>=v[0]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2])
then f[i,j]:=f[i-1,j-v[0]-v[2]]+v[0]*p[0]+v[2]*p[2];
if (j>=v[0]+v[1]+v[2]) and (f[i,j]<f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2])
then f[i,j]:=f[i-1,j-v[0]-v[1]-v[2]]+v[0]*p[0]+v[1]*p[1]+v[2]*p[2];
end;
end;
end;
procedure print;
begin
writeln(f[k,n]);
end;
begin
init;
doit;
print;
end.

o(￣▽￣)o 1A!
Var n,money,p,q,i,j,k,rp:longint;
v,w,f:array[-1000000..1000000] of longint;
b:array[0..1000,0..1000] of longint;
fa:array[1..10000] of boolean;
Function max(a,b:longint):longint;
Begin
If a>b then exit(a) else exit(b);
End;
Begin
readln(money,n);
For i:=1 to n do
Begin
readln(w[i],p,q);
v[i]:=w[i]*p;
If q<>0 then
Begin
inc(b[q,0]);
b[q,b[q,0]]:=i;
End
Else fa[i]:=true;
End;
For i:=1 to n do
Begin
If i=2 then
rp:=maxlongint;
For j:=money downto 0 do
If not fa[i] then break
Else
Begin
If (i=5) and (j=900) then
rp:=maxlongint;
If j-w[i]>=0 then f[j]:=max(f[j],f[j-w[i]]+v[i]);
If b[i,0]=1 then
Begin
If j-w[i]>=0 then f[j]:=max(f[j],f[j-w[i]]+v[i]);
If j-w[i]-w[b[i,1]]>=0 then f[j]:=max(f[j],f[j-w[i]-w[b[i,1]]]+v[i]+v[b[i,1]]);
End;
If b[i,0]=2 then
begin
If j-w[i]>=0 then f[j]:=max(f[j],f[j-w[i]]+v[i]);
If j-w[i]-w[b[i,1]]>=0 then f[j]:=max(f[j],f[j-w[i]-w[b[i,1]]]+v[i]+v[b[i,1]]);
If j-w[i]-w[b[i,2]]>=0 then f[j]:=max(f[j],f[j-w[i]-w[b[i,2]]]+v[i]+v[b[i,2]]);
If j-w[i]-w[b[i,1]]-w[b[i,2]]>=0 then f[j]:=max(f[j],f[j-w[i]-w[b[i,1]]-w[b[i,2]]]+v[b[i,1]]+v[b[i,2]]+v[i]);
End;
End;
End;
Writeln(f[money]);
readln;
End.

请自觉忽略变量rp =.=

var
n,m,n1,i,j,k,ans:longint;
v,p,q,z:array[-1000..10000] of longint;
fu,g:array[0..3201,0..3201] of longint;
f:array[0..10000] of boolean;
begin
readln(n,m); n1:=m; n:=n div 10;
for i:=1 to m do
begin
readln(v[i],p[i],q[i]); v[i]:=v[i] div 10;
p[i]:=v[i]*p[i];
end;
fillchar(f,sizeof(f),true);
for i:=1 to n1 do
if q[i]<>0 then
begin
inc(fu[q[i]][0]); fu[q[i],fu[q[i],0]]:=i;

f[i]:=false;
end;
for i:=1 to n1 do
if f[i] then
begin
if fu[i][0]>=0 then
begin
inc(m); v[m]:=v[i]; p[m]:=p[i]; z[m]:=i;
end;
if fu[i][0]>=1 then
begin
inc(m); v[m]:=v[i]+v[fu[i,1]]; p[m]:=p[i]+p[fu[i,1]]; z[m]:=i;
end;
if fu[i,0]=2 then
begin
inc(m); v[m]:=v[i]+v[fu[i,2]]; p[m]:=p[i]+p[fu[i,2]]; z[m]:=i;
inc(m); v[m]:=v[m-1]+v[m-2]-v[i]; p[m]:=p[m-1]+p[m-2]-p[i];z[m]:=i;
end;
end;
for i:=0 to n do g[n1,i]:=0;
for i:=n1+1 to m do
for j:=v[i] to n do
begin
for k:=n1 to i-1 do
if z[i]<>z[k] then
if g[k,j-v[i]]+p[i]>g[i,j] then g[i,j]:=g[k,j-v[i]]+p[i];
if g[i,j]>ans then ans:=g[i,j];
end;
writeln(ans*10);
end.