Beyond the Void
BYVoid
USACO 3.3.2 Shopping Offers 商店购物

五维的动态规划 状态设置:

F[a1][a2][a3][a4][a5]为买a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5时,所需的最少价格

边界条件:

F[0][0][0][0][0]=0;

状态转移方程:

F[a1][a2][a3][a4][a5]=min{F[ a1-P[i][1] ][ a2-P[i][2] ][ a3-P[i][3] ][ a4-P[i][4] ][ a5-P[i][5] ]+P[i][0])} 其中i=1..s+b; 且 ak-p[i][k]>=0

注意一些特殊数据,如

0 0

之类的

USER: CmYkRgB CmYkRgB [cmykrgb1]
TASK: shopping
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.000 secs, 2880 KB]
   Test 2: TEST OK [0.000 secs, 2884 KB]
   Test 3: TEST OK [0.000 secs, 2884 KB]
   Test 4: TEST OK [0.000 secs, 2880 KB]
   Test 5: TEST OK [0.000 secs, 2880 KB]
   Test 6: TEST OK [0.000 secs, 2884 KB]
   Test 7: TEST OK [0.000 secs, 2880 KB]
   Test 8: TEST OK [0.000 secs, 2884 KB]
   Test 9: TEST OK [0.000 secs, 2884 KB]
   Test 10: TEST OK [0.022 secs, 2884 KB]
   Test 11: TEST OK [0.032 secs, 2880 KB]
   Test 12: TEST OK [0.032 secs, 2884 KB]

All tests OK.

记忆化的递归实现

/*
ID: cmykrgb1
PROG: shopping
LANG: C++
*/
#include <iostream>
#include <fstream>
using namespace std;
ifstream fi("shopping.in");
ofstream fo("shopping.out");
long P[105][6];
long buy[6];
long n,ans;
long c_n[1000];
long F[6][6][6][6][6];
long ori;

void init()
{
	long i,j,m,tp=0,c,k,s,b;
	fi >> s;
	for (i=1;i<=s;i++)
	{
		fi >>m;
		for (j=1;j<=m;j++)
		{
			fi>> c >> k;
			if (c_n[c]==0) c_n[c]=++tp;
			P[i][ c_n[c] ]=k;
		}
		fi >> P[i][0];
	}
	fi >> b;
	for (i=1;i<=b;i++)
	{
		fi>> c >> k >> P[s+i][0];
		if (c_n[c]==0) c_n[c]=++tp;
		P[s+i][ c_n[c] ]=1;
		buy[c_n[c]]=k;
	}
	n=s+b;
	memset(F,0xF,sizeof(F));
	ori=F[0][0][0][0][0];
	F[0][0][0][0][0]=0;
}

void print()
{
	fo << ans <<endl;
	fi.close();
	fo.close();
}

inline long min(long a,long b)
{
	return a<b?a:b;
}

long get(long a1,long a2,long a3,long a4,long a5)
{
	if (F[a1][a2][a3][a4][a5]!=ori)
		return F[a1][a2][a3][a4][a5];
	long i;
	long w1,w2,w3,w4,w5,pmin=ori;
	for (i=1;i<=n;i++)
	{
		w1=a1-P[i][1];w2=a2-P[i][2];w3=a3-P[i][3];w4=a4-P[i][4];w5=a5-P[i][5];
		if (w1<0||w2<0||w3<0||w4<0||w5<0) continue;
		if (F[w1][w2][w3][w4][w5]==ori)
			F[w1][w2][w3][w4][w5]=get(w1,w2,w3,w4,w5);
		pmin=min(pmin,F[w1][w2][w3][w4][w5]+P[i][0]);
	}
	return pmin;
}

int main()
{
	init();
	ans=get(buy[1],buy[2],buy[3],buy[4],buy[5]);
	print();
	return 0;
}

上次修改时间 2017-05-17

相关日志