Home > Old Blog Posts > USACO 3.3.2 Shopping Offers

USACO 3.3.2 Shopping Offers


这是一道很蛋疼的五维完全背包题
设f[a1][a2][a3][a4][a5]为分别买ai(1<=i<=5)种编号为i的商品,所需要的最少金额
初始化:f[a1][a2][a3][a4][a5]=prize[1]*a1+prize[2]*a2+prize[3]*a3+prize[4]*a4+prize[5]*a5
状态转移方程: f[a1][a2][a3][a4][a5]=min{f[a1-count[k][1]][a2-count[k][2]][a3-count[k][3]][a4-count[k][4]][a5-count[k][5]]+cost[k]},其中count[i][j]代表第i种优惠方案所需第j种商品的件数,cost[i]代表第i种优惠方案的总金额

/*
ID: dementr1
PROG: shopping
LANG: C++
*/
#include
#include
using namespace std;
ifstream fin("shopping.in");
ofstream fout("shopping.out");
struct news
{
	int num,c[5],k[5],p;
} fees[100],real[100];
int code[10],amount[10],prize[10],s,b;
bool canuse[100];
void swap(int *a, int *b)
{
	int x;
	x=*a,*a=*b,*b=x;
}
void init()
{
	int i,j;
	memset(fees,0,sizeof(fees));
	memset(canuse,true,sizeof(canuse));
	fin>>s;
	for(i=0;i>fees[i].num;
		for(j=0;j>fees[i].c[j]>>fees[i].k[j];
		fin>>fees[i].p;
	}
	fin>>b;
	for(i=0;i>code[i]>>amount[i]>>prize[i];
	for(i=0;i<b;i++)
		for(j=i+1;jcode[j])
			{
				swap(&code[i],&code[j]);
				swap(&amount[i],&amount[j]);
				swap(&prize[i],&prize[j]);
			}
}
int search(int i)
{
	int j;
	for(j=0;j<b;j++)
		if(code[j]==i)
			return j;
	return -1;
}
void change()
{
	int i,j;
	for(i=0;i<s;i++)
	{
		real[i].num=fees[i].num;
		real[i].p=fees[i].p;
		for(j=0;j<real[i].num;j++)
		{
			int tmp=search(fees[i].c[j]);
			if(tmp==-1)
			{
				canuse[i]=false;
				break;
			}
			real[i].c[tmp]=fees[i].c[j];
			real[i].k[tmp]=fees[i].k[j];
		}
	}
}
void dp()
{
	int f[6][6][6][6][6],a0,a1,a2,a3,a4,i;
	for(a0=0;a0<=amount[0];a0++)
		for(a1=0;a1<=amount[1];a1++)
			for(a2=0;a2<=amount[2];a2++)
				for(a3=0;a3<=amount[3];a3++)
					for(a4=0;a4<=amount[4];a4++)
						f[a0][a1][a2][a3][a4]=prize[0]*a0+prize[1]*a1+prize[2]*a2+prize[3]*a3+prize[4]*a4;
	for(a0=0;a0<=amount[0];a0++)
		for(a1=0;a1<=amount[1];a1++)
			for(a2=0;a2<=amount[2];a2++)
				for(a3=0;a3<=amount[3];a3++)
					for(a4=0;a4<=amount[4];a4++)
						for(i=0;i=0&&
								a1-real[i].k[1]>=0&&
								a2-real[i].k[2]>=0&&
								a3-real[i].k[3]>=0&&
								a4-real[i].k[4]>=0)
								{
									int tmp=f[a0-real[i].k[0]][a1-real[i].k[1]][a2-real[i].k[2]][a3-real[i].k[3]][a4-real[i].k[4]];
									if(tmp+real[i].p<f[a0][a1][a2][a3][a4])
										f[a0][a1][a2][a3][a4]=tmp+real[i].p;
								}
	fout<<f[amount[0]][amount[1]][amount[2]][amount[3]][amount[4]]<<endl;
}
int main()
{
	init();
	change();
	dp();
	return 0;
}
Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: