数据过水 or 灵异事件?
查看原帖
数据过水 or 灵异事件?
361308
Stinger楼主2021/1/4 15:43

在学校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]);
}
2021/1/4 15:43
加载中...