在学校OJ交上去WA八分,洛谷开不开O2都能过?
灵 异 事 件
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
const int P[] = {0, 1, 6, 36, 216, 1296, 7776, 46656};
int w[10005], v[10005], f[10005], cnt, rank[10005];
inline int min(const int x, const int y) {return x < y ? x : y;}
inline int stO_Orz(const int x, const int y) {
int res(0);
for (int i(1); i <= 6; ++ i)
if (x % P[i + 1] / P[i] < y % P[i + 1] / P[i]) return -1;
else res += (x % P[i + 1] / P[i] - y % P[i + 1] / P[i]) * P[i];
return res;
}
struct node {
int c, k, p;
inline bool operator < (const node x) const {return c < x.c;}
};
struct rnm {
struct node {
int c, k;
};
std::vector<node> vec;
int p;
};
std::vector<rnm> vec;
node cnm[10005];
int main() {
memset(f, 0x3f, sizeof f);
int s, b, target(0);
scanf("%d", &s);
for (int i(1); i <= s; ++ i) {
int n;
vec.push_back(rnm{{}, 0});
scanf("%d", &n);
for (int j(1); j <= n; ++ j) {
int c, k;
scanf("%d%d", &c, &k);
vec[i - 1].vec.push_back(rnm::node {c, k});
}
int t;
scanf("%d", &t);
vec[i - 1].p = t;
}
scanf("%d", &b);
for (int i(1); i <= b; ++ i) {
int c, k, p;
scanf("%d%d%d", &c, &k, &p);
cnm[i] = node{c, k, p};
}
f[0] = 0;
std::sort(cnm + 1, cnm + b + 1);
for (int i(1); i <= b; ++ i)
rank[cnm[i].c] = i, cnm[i].c = i, target += cnm[i].k * P[i];
for (auto i : vec) {
++ cnt;
for (auto j : i.vec) w[cnt] += j.k * P[rank[j.c]];
v[cnt] = i.p;
}
for (int i(1); i <= b; ++ i)
for (int j(1); j <= cnm[i].k; ++ j)
w[++ cnt] = j * P[cnm[i].c], v[cnt] = j * cnm[i].p;
for (int i(1); i <= cnt; ++ i)
for (int j(w[i]); j <= target; ++ j) if (stO_Orz(j, w[i]) != -1)
f[j] = min(f[j], f[stO_Orz(j, w[i])] + v[i]);
printf("%d", f[target]);
}