题解 | #购物单#

#include <stdio.h>
#include <string.h>

#define MAX(a,b) ((a>b)?(a):(b))

int main()
{
	int N = 0; //总钱数
	int m = 0;
	scanf("%d %d", &N, &m);
    N /= 10;	//钱数/10，减少循环次数
	/* 商品选项
	1、仅主件					price[m][0]	value[m][0]
	2、主件 + 附件1				price[m][1]	value[m][1]
	3、主件 + 附件2				price[m][2]	value[m][2]
	4、主件 + 附件1 + 附件2		price[m][3]	value[m][3]
	*/
	int price[m][4];	//价格
	int value[m][4]; 	//满意度 = 价格 * 重要度
	memset(price, 0, m*4*sizeof(int));
	memset(value, 0, m*4*sizeof(int));
	
	int v = 0;	//物品价格
	int p = 0;	//重要度(1-5)
	int q = 0;	//主、附件
	
	for(int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &v, &p, &q);
		v /= 10;
		if(q == 0)	//主件
		{
			price[i][0] = v;
			value[i][0] = v * p;
		}
		else
		{
			if(price[q-1][1] == 0)
			{
				//附件1
				price[q-1][1] = v;
				value[q-1][1] = v * p;
			}
			else
			{
				//附件2
				price[q-1][2] = v;
				value[q-1][2] = v * p;
				
				//附件1 + 附件2
				price[q-1][3] = price[q-1][1] + price[q-1][2];
				value[q-1][3] = value[q-1][1] + value[q-1][2];
			}
		}
	}
	
	/* 商品选项赋值 */
	for(int i = 0; i < m; i++)
	{
		for(int j = 1; j < 4; j++)
		{
			price[i][j] += price[i][0];
			value[i][j] += value[i][0];
		}
	}
#if 0
	/* 商品价格打印 */
	for(int i = 0; i < m; i++)
	{
		for(int j = 0; j < 4; j++)
		{
			printf("price[%d][%d] = [%d] ", i, j, price[i][j]);
		}
		printf("\n");
	}
	/* 商品满意度打印 */
	for(int i = 0; i < m; i++)
	{
		for(int j = 0; j < 4; j++)
		{
			printf("value[%d][%d] = [%d] ", i, j, value[i][j]);
		}
		printf("\n");
	}
#endif
	
	/* 用N元钱获取最大的满意度 */
	int dp[m+1][N+1];
	memset(dp, 0, (m+1)*(N+1)*sizeof(int));
	
	int max_value = 0;
	for(int i = 1; i < m+1; i++)
	{
		for(int j = 1; j < N+1; j++)
		{
			max_value = dp[i-1][j];//默认满意度最大的为前i件物品
			for(int k = 0; k < 4; k++)
			{
				if(k > 0 && price[i-1][k] == price[i-1][0])	//说明该物品没有附件
				{
					break;
				}
				if(j - price[i-1][k] >= 0)	//说明N元足够购买当前物品
				{
					max_value = MAX(max_value, dp[i-1][j-price[i-1][k]] + value[i-1][k]);
				}
			}
			dp[i][j] = max_value;
		}
	}
#if 0
    /* 打印所有的满意度 */
    for(int i = 0; i < m+1; i++)
	{
		for(int j = 0; j < N+1; j++)
		{
			printf("dp[%d][%d] = [%d] ", i, j, dp[i][j]);
		}
		printf("\n");
	}
#endif
	printf("%d\n", dp[m][N] * 10);
	return 0;
}