P1064 [NOIP2006 提高组] 金明的预算方案
  • 板块题目总版
  • 楼主windy0321
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/21 14:14
  • 上次更新2024/4/21 15:52:09
查看原帖
P1064 [NOIP2006 提高组] 金明的预算方案
1298142
windy0321楼主2024/4/21 14:14

不知道下面的代码哪里有问题,希望得到大佬解答%%%

#include <bits/stdc++.h>
using namespace std;
struct point
{
	int val,wei;
};
struct node
{
	int cor;
	point par;
	int id1,id2;
	point c1,c2;
}a[61];
point t[301];
int len=1;
int n,m;
int f[3201];
int start;
void func(int i)
{
	start=len;
	t[len].val=a[i].par.val;
	t[len].wei=a[i].par.wei;
	len++;
	if(a[i].id1==1)
	{
		t[len].val=a[i].par.val+a[i].c1.val;
		t[len].wei=a[i].par.wei+a[i].c1.wei;
		len++;
	}
	if(a[i].id2==1)
	{
		t[len].val=a[i].par.val+a[i].c2.val;
		t[len].wei=a[i].par.wei+a[i].c2.wei;
		len++;
		t[len].val=a[i].par.val+a[i].c1.val+a[i].c2.val;
		t[len].wei=a[i].par.wei+a[i].c1.wei+a[i].c2.wei;
		len++;
	}
}
int main()
{
	memset(a,0,sizeof(a));
	cin>>m>>n;
	for(int i=1;i<=n;i++)
	{
		int v,p,q;
		cin>>v>>p>>q;
		v/=10;
		a[i].cor=q;
		if(q==0)
		{
			a[i].par.wei=v;
			a[i].par.val=p*v;
		}
		else
		{
			if(a[q].id1==0)
			{
				a[q].id1=1;
				a[q].c1.wei=v;
				a[q].c1.val=p*v;
			}
			else
			{
				a[q].id2=1;
				a[q].c2.wei=v;
				a[q].c2.val=p*v;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(a[i].cor!=0)
		{
			continue;
		}
		func(i);
		cout<<start<<endl;
		for(int j=m;j>=a[i].par.wei;j--)
		{
//			f[i][j]=f[i-1][j];
//			if(a[i].cor!=0)
//			{
//				continue;
//			}
			for(int k=len-1;k>=start;k--)
			{
				if(t[k].wei<=j)
				{
					f[j]=max(f[j],f[j-t[k].wei]+t[k].val);
				}
			}
		}
	}
	cout<<10*f[m]<<endl;
	return 0;
}
2024/4/21 14:14
加载中...