呼~今天去學(xué)校啦！早上7點起床寫題，挑了個簡單題寫 ^_^
這個是IOI95的DP題。用一個b位的6進制數(shù)i表示狀態(tài)。這個6進制數(shù)的每一位分別表示相應(yīng)物品的數(shù)量。f[i]表示狀態(tài)i下的最小花費。同樣也可以用6進制數(shù)j表示優(yōu)惠。那么，f[i]就能轉(zhuǎn)移到f[i - j]，如果優(yōu)惠j可用的話。代價是使用優(yōu)惠j時減少的花費。最后的答案就是min(f[i])，0 <= i <= start（start是初始狀態(tài)）。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-9-4 7:35:59
File Name: pku1170.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout << #x << ": " << x << endl)
const int maxint = 0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template <class T> void show(T a, int n) 
{for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }
template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }
const int maxn = 5;
int b, s;
int mark[1000];
int num[maxn], price[maxn];
int reduce[100][maxn];
int reduce_price[100];
void to_array(int a, int array[])
{
for (int i = 0; i < b; i++)
{
array[i] = a % 6;
a /= 6;
}
}
void to_num(int &a, int array[])
{
a = 0;
for (int i = b - 1; i >= 0; i--)
{
a += array[i];
a *= 6;
}
a /= 6;
}
int reduce_state(int item[], int reduce[])
{
for (int i = 0; i < b; i++)
if (item[i] < reduce[i])
return 0;
for (int i = 0; i < b; i++)
item[i] -= reduce[i];
return 1;
}
const int maxp = 6*6*6*6*6;
int f[maxp];
int dp()
{
for (int i = 0; i < maxp; i++)
f[i] = maxint;
int start;
to_num(start, num);
int start_price = 0;
for (int i = 0; i < b; i++)
start_price += num[i] * price[i];
f[start] = start_price;
for (int i = start; i >= 0; i--) if (f[i] < maxint)
{
int now_num[maxn];
for (int j = 0; j < s; j++)
{
to_array(i, now_num);
if (reduce_state(now_num, reduce[j]))
{
int t;
to_num(t, now_num);
f[t] <?= f[i] - reduce_price[j];
}
}
}
int ret = maxint;
for (int i = 0; i <= start; i++)
ret <?= f[i];
return ret;
}
int main()
{
scanf("%d", &b);
memset(mark, -1, sizeof(mark));
for (int i = 0; i < b; i++)
{
int t;
scanf("%d", &t);
mark[t] = i;
scanf("%d%d", &num[i], &price[i]);
}
scanf("%d", &s);
for (int i = 0; i < s; i++)
{
int t;
scanf("%d", &t);
int t1, t2, sum = 0;
for (int j = 0; j < t; j++)
{
scanf("%d%d", &t1, &t2);
reduce[i][mark[t1]] = t2;
sum += price[mark[t1]] * t2;
}
scanf("%d", &t);
reduce_price[i] = sum - t;
}
printf("%d\n", dp());
return 0;
}