|
|
思路：
由于一共有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;
}
|