Desc.
有 $N$ 个商品, 每个商品有个种类 $a_i$, 有个价格 $c_i$.
对于第 $j$ 个种类, 必须购买个数位于 $[x_j,y_j]$ 的商品, 即最少购买 $x_j$ 个, 最多购买 $y_j$ 个该种类的商品.
您需要求出前 $K$ 种便宜的方案所需的价钱, 如果没有这样的方案, 请输出 -1.
Sol.
学习了 command_block 做法.
让我们用 $S$ 来表示一个方案, $\mathrm {trans} (S)$ 表示 $S$ 的后继 (不优于 $S$ 的方案, 具体有哪些需据情况而定). 如果 $\mathrm {trans} (S)$ 包含所有的后继显然是不优的. 对于这类题目, 我们要做的就是优化 $\mathrm {trans} (S)$ 的定义 (或构造方式) 使得其大小被时空限制所接受.
本题可以被分为两个部分, 分别是「$m = 1$」和「$l = r$」. 因为如果解决了后者, 我们就可以在此基础上用前者来求出答案了. 具体的优化过程就略过不述了, 仅作为方法在此记录.
const int N = 2e5;
const ll INF = 1.01e18;
struct Getter {
struct Tuple {
int x, y, z;
ll w;
Tuple(int _x, int _y, int _z, ll _w)
: x(_x), y(_y), z(_z), w(_w) {}
bool operator<(const Tuple& rhs) const { return w > rhs.w; }
};
vll cseq;
vi seq;
priority_queue<Tuple> decisions;
int _n;
int lower, upper;
void init() {
_n = seq.size();
sort(allu(seq));
if (lower > _n) return void(cseq = vll{INF, INF});
chkmin(upper, _n);
decisions.emplace(lower-2, lower-1, _n-1,
accumulate(&seq[0], &seq[lower], 0ll));
next(0), next(1);
}
void next(int k) {
if (k < (int)cseq.size()) return;
if (decisions.empty()) return void(cseq.pb(INF));
const auto [x, y, z, w] = decisions.top();
decisions.pop();
cseq.pb(w);
if (z == _n-1 && x+1 == y && y+1 < upper)
decisions.emplace(x+1,y+1, z, w+seq[y+1]);
if (y >= 0 && y+1 <= z)
decisions.emplace(x, y+1, z, w-seq[y]+seq[y+1]);
if (x >= 0 && x+1 < y)
decisions.emplace(x-1, x+1, y-1, w-seq[x]+seq[x+1]);
}
} total[N+5];
struct Decision {
int p, idx;
ll w;
Decision(int _p, int _i, ll _w)
: p(_p), idx(_i), w(_w) {}
bool operator<(const Decision& rhs) const { return w > rhs.w; }
};
int n, m, k;
int main() {
ignore = freopen("plan.in", "r", stdin);
ignore = freopen("plan.out", "w", stdout);
ios::sync_with_stdio(0);
IN.tie(nullptr);
IN > n > m > k;
for (int i=0,fu,ck;i<n;++i)
IN > fu > ck, total[fu].seq.pb(ck);
for (int i=1;i<=m;++i)
IN > total[i].lower > total[i].upper;
for (int i=1;i<=m;++i)
total[i].init();
sort(total+1, total+m+1, [&](const Getter& lhs, const Getter& rhs) {
return lhs.seq[1]-lhs.seq[0] < rhs.seq[1]-rhs.seq[0];
});
priority_queue<Decision> heap; {
ll s0 = 0;
for (int i=1;i<=m;++i)
s0 += total[i].cseq[0], chkmin(s0, INF);
heap.emplace(0, 0, s0);
}
int fuck = 0;
while (fuck < k && !heap.empty()) {
const auto [p, idx, w] = heap.top();
heap.pop();
if (w >= INF) break;
OUT < w < "\n"; ++fuck;
if (p < m && idx == 1)
heap.emplace(p+1, 1, w-total[p].cseq[1]+total[p].cseq[0]-total[p+1].cseq[0]+total[p+1].cseq[1]);
if (p < m)
heap.emplace(p+1, 1, w-total[p+1].cseq[0]+total[p+1].cseq[1]);
if (p >= 1) {
total[p].next(idx+1);
heap.emplace(p, idx+1, w-total[p].cseq[idx]+total[p].cseq[idx+1]);
}
}
for (;fuck<k;++fuck) OUT < "-1\n";
}/ When that I was young and a little tiny boy, /
/ With hey, ho, the wind and the rain, /
/ A foolish thing was but a toy, /
/ For the rain it raineth every day. /