正文
USACO Training 3.3 商店购物 By cellur925
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
题目传送门
这道题有着浓浓的背包气氛。所以我们可以这样想:可以把每个优惠方案都当做一个物品,每个单买所需要花的钱也当做一个物品。(也就是代码中的p结构体数组)而且基于此题的环境,这题是一个完全背包。
另外因为本题的算法比较亲民,至多买5种物品,每种物品最多买5个,所以我们可以(开创性地)使用五维背包。
状态:设f[i][j][k][a][b]表示买i件物品1,j件物品2,k件物品3,a件物品4,b件物品5所需要的最小价钱。(也就是说,我们熟悉的背包模板中f[i]中i的含义从体积在此题背景下变成了购买个数)
转移:f[i][j][k][a][b]=min(f[i][j][k][a][b],f[i-p[pos].cnt[1]][j-p[pos].cnt[2]][k-p[pos].cnt[3]][a-p[pos].cnt[4]][b-p[pos].cnt[5]]+p[pos].val);
边界:f[0][0]=0,其余为正无穷。(这种条件有时必要有时不必要,需要 具体分析)
将繁琐的数据输入处理后,我们就开始进行背包了。
但有一点需要注意,也是本题的重难点(之一)。也就是各个物品的编号给他转成1~5.但是其实数据已经约定了,购买方案中涉及到的产品应该也都是要买的。
所以每组数据涉及到的物品也就最多5个。
* 本题其实还可以用最短路做,这也是我之前比较倾向的算法。但是如何把各种购买方案映射好,却是一个难题。所以放弃了==
(@Sarah :每个节点的标号可以映射成一个篮子的物品个数情况,每一个优惠方式(包括以物品原价购买)表示一条边,权值就是花费,所以就是求一个从空篮子到目标篮子的最短路径。)
Code
/*
ID:cellur_2
TASK:shopping
LANG:C++
*/
#include<cstdio>
#include<algorithm>
#include<map> using namespace std;
const int inf=0x3f3f3f3f; int s,n,b,t;
int real[];
int f[][][][][];
struct goods{
int val;
int n;
int cnt[];
}p[];
map<int,int>m; void init()
{
for(int i=;i<=;i++)
for(int j=;j<=;j++)
for(int k=;k<=;k++)
for(int a=;a<=;a++)
for(int b=;b<=;b++)
f[i][j][k][a][b]=inf;
f[][][][][]=;
} int main()
{
freopen("shopping.in","r",stdin);
freopen("shopping.out","w",stdout);
scanf("%d",&s);
for(int i=;i<=s;i++)
{
scanf("%d",&n);
p[i].n=n;
for(int j=;j<=n;j++)
{
int c=,k=;
scanf("%d%d",&c,&k);
if(m[c]==) t++,m[c]=t;
p[i].cnt[m[c]]=k;
}
scanf("%d",&p[i].val);
}
scanf("%d",&b);
for(int i=;i<=b;i++)
{
s++;
int a=,d=,e=;
scanf("%d%d%d",&a,&d,&e);
if(m[a]==) t++,m[a]=t;
p[s].n=,p[s].val=e,p[s].cnt[m[a]]=;
real[m[a]]=d;
}
init();
for(int pos=;pos<=s;pos++)
for(int i=p[pos].cnt[];i<=real[];i++)
for(int j=p[pos].cnt[];j<=real[];j++)
for(int k=p[pos].cnt[];k<=real[];k++)
for(int a=p[pos].cnt[];a<=real[];a++)
for(int b=p[pos].cnt[];b<=real[];b++)
f[i][j][k][a][b]=min(f[i][j][k][a][b],f[i-p[pos].cnt[]][j-p[pos].cnt[]][k-p[pos].cnt[]][a-p[pos].cnt[]][b-p[pos].cnt[]]+p[pos].val);
printf("%d\n",f[real[]][real[]][real[]][real[]][real[]]);
return ;
}