NOI 2006:金明の予算案

タイトルリンク:http://www.rqnoj.cn/Status_Show.asp?SID=744089
この問題は2、3日葛藤して、主に主件と添付ファイルの関係で、それから問題を選んで人を葛藤させます.私たちはマスターと対応する添付ファイルをグループ化することができて、各グループに対して、私达は以下のいくつかの选択の方式があって、すべて选ばないで、マスターだけを选んで、マスターと1つの添付ファイルを选んで、マスターと複数の添付ファイルを选んで、题意によって、各グループは最大で4种类の情况があって、ここで直接列挙することができて、このいくつかの选択は互いに相容れないので、このようにパケットのリュックサックの问题に転化します.では、次のプログラミングは比較的簡単です.
パケットバックパックのゲージ方程式:f(k,v)=max{f(k−1,v),f(k−1,v−c[i])+w[i]であり,アイテムiはパケットk}に属し,f(k,v)はバックパック容量がvであることを示し,前のkからいくつかのアイテムを選択して最大値を得た.実はこのテーマは直接依存するリュックサックの問題で、一般的にはまず対応するグループに転化して、グループのリュックサックの問題になって、グループごとに1回01リュックサックの問題を行うことができます.
コードは次のとおりです.

#include 
#include 
#include 
#include 
#include 
using namespace std ;

const int maxn = 3205 ;

struct Node
{
	int p ;
	int c ;
	int w ;
	int in ;
};

int dp[65][maxn] ;
deque v1[65];
Node pack_node[65][65] ;

int m ;
int n ;
int num ;

void input();
void work() ;
void init() ;

int main()
{
	work()   ;
	return 0 ;
}

void work()
{

	int i ;
	int v ;
	int k ;

	for(i = 0 ; i < 65 ; i ++)
		v1[i].clear() ;

	memset(dp , 0 , sizeof(dp)) ;
	memset(pack_node , 0 ,sizeof(pack_node)) ;

	//freopen("data.in" , "r" , stdin) ;

	input() ;
	init() ;

	for(i = 1 ; i <= num ; i ++)
	{
		for( v = m ; v >= 0 ; v--)
		{
			dp[i][v] = dp[i-1][v] ;

			for(k = 0 ; v >= pack_node[i][k].c && k < 4 ; k ++)
			{
				if(dp[i][v] < dp[i-1][v - pack_node[i][k].c] + pack_node[i][k].w)
				{
					dp[i][v] = dp[i-1][v - pack_node[i][k].c] + pack_node[i][k].w ;
				}
			}
		}
	}

	printf("%d
" , dp[num][m] * 10) ;
}
void  input()
{
	int i ;
	int j ;
	Node a ;

	scanf("%d%d" , &m , &n) ;
	m = m / 10 ;
	num = 0 ;

	for(i = 1 ; i <= n ; i ++)
	{
		scanf("%d%d%d" ,&a.c , &a.w , &a.p ) ;
		a.in  = i ;

		a.c = a.c / 10 ;

		if(a.p==0)
			v1[++num].push_front(a) ;

		else
		{
			for( j = 1 ; j <=num ; j ++)
				if(v1[j][0].in == a.p)
					break ;

			v1[j].push_back(a) ;
		}
	}
}

void init()
{
	int i ;
	int len ;
	for(i = 1 ; i <= num ; i ++)
	{
		len = v1[i].size() ;

		if(len>=1)
		{
				pack_node[i][0].c = v1[i][0].c ;
				pack_node[i][0].w = v1[i][0].c * v1[i][0].w ;

		}
		if(len>=2)
		{
			pack_node[i][1].c = pack_node[i][0].c + v1[i][1].c ;
			pack_node[i][1].w = pack_node[i][0].w + v1[i][1].c * v1[i][1].w ;
		}

		if(len==3)
		{
			pack_node[i][2].c = pack_node[i][0].c + v1[i][2].c ;
			pack_node[i][2].w = pack_node[i][0].w + v1[i][2].c * v1[i][2].w ;
			pack_node[i][3].c = pack_node[i][1].c + v1[i][2].c ;
			pack_node[i][3].w = pack_node[i][1].w + v1[i][2].c * v1[i][2].w ;
		}
	}
}