A，B，C，D依旧水
E题观察到答案转移的区间是一个后缀，且满足单调性，可以单调队列维护，但我写二分过了
#include <bits/stdc++.h>
using namespace std;
long long n, dp[1005][1005], maa[1005][1005], ans, l, r, mid, dp2[1005][1005], maa2[1005][1005];
struct sd {
long long x, p;
} a[1005];
int cmp(sd A, sd B) { return A.x < B.x; }
int cmp2(sd A, sd B) { return A.x > B.x; }
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].p;
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (i == j)
dp[i][j] = a[i].p;
else {
l = 1, r = j;
while (l < r) {
mid = (l + r) / 2;
if (a[j].x - a[mid].x <= a[i].x - a[j].x) {
r = mid;
} else
l = mid + 1;
}
dp[i][j] = maa[j][l] + a[i].p;
}
}
maa[i][i] = dp[i][i];
for (int j = i - 1; j >= 1; j--) {
maa[i][j] = max(maa[i][j + 1], dp[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
ans = max(ans, dp[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = 0;
maa[i][j] = 0;
}
}
sort(a + 1, a + n + 1, cmp2);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (i == j)
dp[i][j] = a[i].p;
else {
l = 1, r = j;
while (l < r) {
mid = (l + r) / 2;
if (abs(a[j].x - a[mid].x) <= abs(a[i].x - a[j].x)) {
r = mid;
} else
l = mid + 1;
}
dp[i][j] = maa[j][l] + a[i].p;
}
}
maa[i][i] = dp[i][i];
for (int j = i - 1; j >= 1; j--) {
maa[i][j] = max(maa[i][j + 1], dp[i][j]);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
ans = max(ans, dp[i][j]);
}
}
cout << ans;
return 0;
}
F题正常思路是dp[i][j]表示i走j步能到的最远点，发现肯定超时，于是可以用倍增dp，把j分为2^0,2^1,2^2…….，就能到nlogn
#include <bits/stdc++.h>
using namespace std;
int n, k, f[2000000][25];
struct sb {
int l, r;
} a[2000005];
bool cmp(sb x, sb y) { return x.l < y.l; }
int solve(int l, int r) {
int p = l, anss = 0;
for (int j = 21; j >= 0; j--) {
if (f[p][j] <= r && f[p][j] > p) {
p = f[p][j];
anss += 1 << j;
}
}
if (p <= r) {
p = f[p][0];
anss++;
}
if (p >= r + 1)
return anss;
else
return 114514191;
}
int main() {
cin >> n >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i].l >> a[i].r;
if (a[i].l > a[i].r)
a[i].r += n;
}
sort(a + 1, a + 1 + k, cmp);
int p = 1, r = -1;
for (int i = 1; i <= 2 * n; i++) {
while (p <= k && a[p].l <= i) {
r = max(r, a[p].r);
p++;
}
f[i][0] = r + 1;
}
for (int j = 1; j <= 21; j++) {
for (int i = 1; i <= 2 * n; i++) {
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
int ans = 114514191, rr;
for (int l = 1; l <= n; l++) {
rr = l + n - 1;
ans = min(ans, solve(l, rr));
}
if (ans == 114514191) {
cout << "impossible";
return 0;
}
cout << ans;
return 0;
}
G题费用流加线段树优化建图，又炸了
（为什么费用流还有过部分点的啊啊啊啊啊啊）
有大佬帮忙看看吗？
#include <bits/stdc++.h>
using namespace std;
long long n, a[5005], b[5005], c[5005], maa, work[1000005], head[1000005], nex[1000005], u[1000005],
v[1000005], w[1000005], co[1000005], id, st = 0, en = 30005, cnt[1000005], L, R, tmp, aa, bb, top,
vis[1000005], flo[1000005], ans, cost, tru[1000005],
pre[1000005];
struct sd {
long long l, r, maxx;
} tree[4000005];
queue<int> q;
bool spfa() {
for (long long i = 0; i <= en; i++) {
cnt[i] = 999999999999;
tru[i] = 0;
}
q.push(0);
cnt[st] = 0;
tru[st] = 1;
while (!q.empty()) {
long long y = q.front();
tru[y] = 0;
q.pop();
for (long long i = head[y]; i != -1; i = nex[i]) {
long long hk = v[i];
if (cnt[y] + co[i] < cnt[hk] && w[i] > 0) {
pre[hk] = i;
flo[hk] = min(flo[y], w[i]);
cnt[hk] = cnt[y] + co[i];
if (tru[hk] == 0) {
q.push(hk);
tru[hk] = 1;
}
}
}
}
// for(long long i=0;i<=en;i++) cout<<cnt[i]<<endl;
// return 0;
if (cnt[en] == 999999999999)
return 0;
return 1;
}
long long dfs(long long x, long long flow) {
// cout<<"2";
vis[x] = 1;
if (x == en)
return flow;
// cout<<ans<<" ";
for (long long &i = work[x]; i != -1; i = nex[i]) {
long long y = v[i];
if (w[i] > 0 && pre[y] == x && vis[y] == 0) {
tmp = dfs(y, min(flow, w[i]));
if (tmp > 0) {
w[i] -= tmp;
w[i ^ 1] += tmp;
cost += tmp * (-co[i]);
return tmp;
}
}
}
return 0;
}
void add(long long xx, long long yy, long long zz, long long zzz) {
u[top] = xx, v[top] = yy;
w[top] = zz;
co[top] = zzz;
nex[top] = head[u[top]];
head[u[top]] = top;
top++;
}
void dinico() {
while (spfa() != 0) {
// cout<<"-1";
// for (long long i = 0; i <= en; i++) work[i] = head[i];
// while (1) {
// flo = 0;
// for (long long i = 0; i <= en; i++) vis[i] = 0;
// flo = dfs(st, 11451419);
// if (flo == 0)
// break;
// ans += flo;
// }
ans += flo[en];
cost -= flo[en] * cnt[en];
int hgx = en, lsd;
while (hgx != st) {
lsd = pre[hgx];
w[lsd] -= flo[en];
w[lsd ^ 1] += flo[en];
hgx = u[lsd];
}
}
return;
}
void build(long long ll, long long rr, long long kl) {
id = max(id, kl);
tree[kl].l = ll;
tree[kl].r = rr;
if (ll == rr) {
add(kl, en, 1, 0);
add(en, kl, 0, 0);
return;
}
long long mid = (ll + rr) / 2;
add(kl, kl * 2, mid - ll + 1, 0);
add(kl * 2, kl, 0, 0);
add(kl, kl * 2 + 1, rr - mid + 1, 0);
add(kl * 2 + 1, kl, 0, 0);
build(ll, mid, kl * 2);
build(mid + 1, rr, kl * 2 + 1);
}
void wok(long long sg, long long cl, long long cr, long long kl, long long gb) {
if (cl > cr)
return;
long long ans = 0;
if (cl == tree[kl].l && cr == tree[kl].r) {
add(sg, kl, 1, gb);
add(kl, sg, 1, -gb);
return;
}
long long ll = tree[kl].l, rr = tree[kl].r;
long long mid = (ll + rr) / 2;
if (cl <= mid && cr > mid) {
wok(sg, cl, mid, kl * 2, gb);
wok(sg, mid + 1, cr, kl * 2 + 1, gb);
} else {
if (cr <= mid)
wok(sg, cl, cr, kl * 2, gb);
if (cl > mid)
wok(sg, cl, cr, kl * 2 + 1, gb);
}
}
int main() {
cin >> n;
for (long long i = 0; i <= en; i++) {
head[i] = nex[i] = -1;
flo[i] = 999999999;
}
for (long long i = 1; i <= n; i++) {
cin >> a[i] >> b[i] >> c[i];
maa = max(maa, b[i] - 1);
}
build(1, maa, 1);
for (long long i = 1; i <= n; i++) {
add(0, id + i, 1, 0);
add(id + i, 0, 0, 0);
}
//
for (long long i = 1; i <= n; i++) {
wok(i + id, a[i], b[i] - 1, 1, -c[i]);
add(i + id, en, 1, 0);
add(en, i + id, 0, 0);
}
// cout<<"1";
dinico();
cout << cost;
return 0;
}