[蓝桥杯][算法提高VIP]促销购物

题目

题目链接

题解

动态规划。

看到底下的标签是动态规划之后，仔细一想确实可以转换为完全背包问题，但是背包开几维啊，每一维的容量可以表示为所需物品的最大件数，但是物品有999种啊。 这时，我们的突破口就应该放在最多购买5种不同的商品上，这样我们只需要五维就可以控制选的五种商品了。 与经典背包不同这个是求最小值，因此初始化非常关键。

开始用的dfs实现的，无论怎么优化只能过89，剩下的超时，不知道原因。

代码

#include
using namespace std;
const int N = 1010;

struct SALE { // 促销活动的信息 
	int num[N]; // num[i] 表示此促销活动要求买编号为i的商品多少个 
	int p; // 此促销方式的价格 
} sale[N]; // sale[i] 表示第i种促销方式 

struct BUY { // 顾客要买的商品 
	int c, k, p; // 编号、数量、单价 
} buy[6]; // buy[i] 表示要买的第i种商品（并非编号为i的商品）的信息 

int s, n, b, c, k, p;
int ans[6][6][6][6][6]; // ans[i(1)][i(2)][i(3)][i(4)][i(5)] 表示购买i(j)件第j种商品（并非编号为j的商品）的最小花费，其中j=1~5 

int main()
{
	cin>>s;
	for(int i = 1;i >n;
		for(int j = 1;j >c>>k, sale[i].num[c] = k;
		cin>>sale[i].p;
	}
	cin>>b;
	for(int i = 1;i >c>>k>>p;
		buy[i].c = c, buy[i].k = k, buy[i].p = p;
		// 还需要保存每个单件物品，也算是一种促销方式；等价于背包问题中的一类物品 
		sale[++s].num[c] = 1; // 无法用折扣，因此每个商品都按单价算 
		sale[s].p = p;
	}
	
	// 背包问题求最小值的初始化方式 
	memset(ans, 0x3f, sizeof ans);
	ans[0][0][0][0][0] = 0;
	
	for(int i = 1;i