1155.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"vector"
#include"utility"
using namespace std;

typedef pair<int,int> edge;
vector<edge> e[3002];
int n,m,money[3002];

int merge(int ans1[3002],int ans2[3002],int ans[3002],int s1,int s2,int value)
{
	int i,j;
	for(i=0;i<=s1+s2;i++)
	{
		if(i<=s1)ans[i]=ans1[i];
		else ans[i]=-99999999;
		
		if(i<=s2&&ans2[i]-value>ans[i])
			ans[i]=ans2[i]-value;

		for(j= (1<i-s2?i-s2:1) ;j<=s1&&j<i;j++)
		{
			if(ans1[j]+ans2[i-j]-value>ans[i])
				ans[i]=ans1[j]+ans2[i-j]-value;
		}
	}
	return s1+s2;
}

int dp(int a,int ans[3002])
{
	int i,ans1[3002],ans2[3002],s1,s2;
	if(a>n-m)
	{
		ans[0]=0;
		ans[1]=money[a];
		return 1;
	}
	else
	{
		ans1[0]=0;s1=0;
		for(i=0;i<e[a].size();i++)
		{
			s2=dp(e[a][i].first,ans2);
			s1=merge(ans1,ans2,ans,s1,s2,e[a][i].second);
			copy(ans,ans+s1+1,ans1);
		}
		return s1;
	}
}

void init()
{
	int i,j,k;
	cin>>n>>m;
	for(i=1;i<=n-m;i++)
	{
		cin>>k;
		e[i].resize(k);
		for(j=0;j<k;j++)
		{
			cin>>e[i][j].first>>e[i][j].second;
		}
	}

	for(i=n-m+1;i<=n;i++)
		cin>>money[i];
}

int main()
{
	int ans[3002],i,k;
	init();
	dp(1,ans);
	for(i=0;i<=m;i++)
	{
		if(ans[i]>=0)
			k=i;
	}

	cout<<k<<endl;

	return 0;
}