呼~今天去学校啦!早上7点起床写题,挑了个简单题写 ^_^
这个是IOI95的DP题。用一个b位的6进制数i表示状态。这个6进制数的每一位分别表示相应物品的数量。f[i]表示状态i下的最小花费。同样也可以用6进制数j表示优惠。那么,f[i]就能转移到f[i - j],如果优惠j可用的话。代价是使用优惠j时减少的花费。最后的答案就是min(f[i]),0 <= i <= start(start是初始状态)。

/**//*************************************************************************
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;
}