[NOIP2006]金明的预算方案

第1行，为两个正整数，用一个空格隔开：N m（其中N（ < 32000 ）表示总钱数，m（ < 60 ）为希望购买物品的个数。）
从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有3个非负整数v p q（其中v表示该物品的价格（v < 10000），p表示该物品的重要度（1~5），q表示该物品是主件还是附件。如果q=0，表示该物品为主件，如果q>0，表示该物品为附件，q是所属主件的编号）

C++14(g++5.4) 解法, 执行用时: 6ms, 内存消耗: 728K, 提交时间: 2019-09-21 10:18:56

#include <iostream>
using namespace std;
int n,m,f[5000010],h[5000010];
struct node
{
	int v,p,q;
}a[1010];
int main()
{
	cin>>n>>m;
	int i,j,k;
	for(i=1;i<=m;i++)
	{
		cin>>a[i].v>>a[i].p>>a[i].q;
		a[i].p*=a[i].v;
	}
	for(i=1;i<=m;i++)
	{
		if(a[i].q==0)
		{
			for(j=1;j<a[i].v;j++)
				h[j]=0;
			for(j=a[i].v;j<=n;j++)
				h[j]=f[j-a[i].v]+a[i].p;
			for(j=1;j<=m;j++)
				if(a[j].q==i)
					for(k=n;k>=a[i].v+a[j].v;k--)
						h[k]=max(h[k],h[k-a[j].v]+a[j].p);
			for(j=a[i].v;j<=n;j++)
				f[j]=max(f[j],h[j]);
		}
	}
	cout<<f[n];
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 648K, 提交时间: 2023-01-03 16:33:09

#include <bits/stdc++.h>
using namespace std;
int n,m;
int p[100], q[100], v[100], f[32222] , g[32222] ;
int main(void)
{
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		cin >> v[i] >> p[i] >> q[i];
		p[i] *= v[i];
	}
	for(int i=1;i<=m;i++){
		if(q[i]) continue;
		for(int j=v[i];j<=n;j++) g[j] = f[j-v[i]]+p[i];
		for(int j=1;j<=m;j++){
			if(q[j]==i){
				for(int k=n;k>=v[i]+v[j];k--)
					g[k] = max(g[k],g[k-v[j]]+p[j]);
			}
		}
		for(int j=0;j<=n;j++) f[j] = max(g[j],f[j]);
	}
	cout << f[n];
	return 0;
}

详情