|
|
思路：
由于一共有5种物品，每种物品最多只能有5个，所以物品的拥有情况，可以表示为 6*6*6*6*6 中状态。
这个数好像是 7k 多，不大。
状态转移发生在有折扣的时候，如果当前的状态可以打折，那么就看打折之后是否会比现在划算就可以了。
一开始用的是取模，后来改成位操作了，快了一点，但还是很慢，不明白那些0ms怎么来的，⊙﹏⊙b汗
代码很烂，仅供参考
 #include <stdio.h>
int S, B;
int price[1024], code[1024];
int offer[128], cut[128];
int ans[1 << 15];
inline int min(int a, int b)
   {
 return a < b ? a : b;
 }
int main()
{
int c, k, i, j, n, t, m[5], a, b;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &B);
t = 0;
  for (i = 0; i < B; i++) {
scanf("%d%d%d", &c, &k, &price[i]);
t |= k << (i*3);
code[c] = i;
 }
scanf("%d", &S);
for (i = 0; i < S; i++) {
scanf("%d", &n);
offer[i] = 0;
while (n--) {
scanf("%d%d", &c, &k);
offer[i] |= k << (code[c]*3);
}
scanf("%d", &cut[i]);
}
for (i = 0; i <= t; i++) {
ans[i] = 0;
a = i;
for (j = 0; j < B; j++) {
ans[i] += price[j] * (a & 7);
a >>= 3;
}
for (j = 0; j < S; j++) {
a = i;
b = offer[j];
for (k = 0; k < B; k++) {
if ((a & 7) < (b & 7))
break;
a >>= 3;
b >>= 3;
}
if (k < B)
continue;
ans[i] = min(ans[i], ans[i - offer[j]] + cut[j]);
}
}
printf("%d\n", ans[t]);
return 0;
}
|