这道题的 的做法还是挺不好想的这里不赘述可以看弱化版 P2365 的题解。大概思路是先把每个 的代价提前计算再加上前缀和优化。用 和 表示 和 的前缀和那么可以写出 做法化简一下就可以很容易化出一次函数的形式果断使用李超线段树需要离散化或动态开点。代码#includebits/stdc.h #define int long long using namespace std; const int N 3e5 5; int n, s, len, tot, f[N], t[N], sumf[N], sumt[N], a[N], tg[4 * N], dp[N]; struct line{ int k, b; line(int x 0, int y 0){ k x; b y; } }l[N]; int g(int x){ return lower_bound(a 1, a len 1, x) - a; } int F(int x, int id){ return l[id].k * x l[id].b; } void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(F(a[mid], id) F(a[mid], v)) swap(id, v); if(F(a[l], id) F(a[l], v)) update(2 * x, l, mid, id); if(F(a[r], id) F(a[r], v)) update(2 * x 1, mid 1, r, id); } int query(int x, int l, int r, int k){ if(l k || r k) return 1e18; int ans F(a[k], tg[x]); if(l r) return ans; int mid (l r) 1; if(k mid) return min(ans, query(2 * x, l, mid, k)); return min(ans, query(2 * x 1, mid 1, r, k)); } signed main(){ cin n s; for(int i 1; i n; i){ cin t[i] f[i]; sumt[i] sumt[i - 1] t[i]; sumf[i] sumf[i - 1] f[i]; a[i] sumt[i]; } sort(a 1, a 1 n); len unique(a 1, a n 1) - a - 1; for(int i 1; i n; i){ dp[i] sumf[n] * s sumf[i] * sumt[i] query(1, 1, len, g(sumt[i])); l[tot] line(-sumf[i], dp[i] - sumf[i] * s); update(1, 1, len, tot); } cout dp[n]; return 0; }P5896wqs二分被称为Aliens Trick的出处。所以显然需要前置芝士wqs二分我这里面应该有一篇详细讲了一下这道题就不详细讲wqs二分了。考虑一个坐标为的兴趣点会被怎样的拍摄区域覆盖对于每一个正方形用 表示 表示 可以发现如果有一个左上角方格坐标为 右下角坐标为 的拍摄区域因为一定在主对角线上所以这两个方格的横纵坐标相等当 且 时这个拍摄区域可以覆盖这个兴趣点。这时我们就可以转化一下题意数轴上有 个范围分别为 的区间你要新建 个区间去覆盖一开始的区间新建一个覆盖范围为 的区间的代价为 求最小代价。显然在一开始就已经被其他区间覆盖的区间是没有用的因为覆盖它的区间被覆盖它也就会被覆盖。类似于P6047丝之割把没用的区间去除剩下的区间 单调递增 也单调递增。考虑wqs二分去掉 个限制写出 式子这里是去除重复覆盖展开显然可以斜率优化。由于本题时限为2s所以李超线段树随便过。本题可以不用离散化。代码#includebits/stdc.h #define pi pairint, int #define int long long using namespace std; const int N 1e5 5; int n, m, k; int ans, tot, cnt, len, tg[4 * N], dp[N], s[N], a[N]; struct line{ int k, b; line(int x 0, int y 0){ k x, b y; } }l[N]; struct node{ int l, r; }b[N], c[N]; inline bool cmp(node a, node b){ if(a.l b.l) return a.r b.r; return a.l b.l; } inline int g(int x){ return lower_bound(a 1, a len 1, x) - a; } inline int f(int x, int id){ return l[id].k * x l[id].b; } inline void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(f(a[mid], id) f(a[mid], v)) swap(v, id); if(f(a[l], id) f(a[l], v)) update(2 * x, l, mid, id); if(f(a[r], id) f(a[r], v)) update(2 * x 1, mid 1, r, id); } inline pi query(int x, int l, int r, int k){ pi out; out.first f(a[k], tg[x]); out.second tg[x]; if(l r) return out; int mid (l r) 1; if(k mid) return min(out, query(2 * x, l, mid, k)); else return min(out, query(2 * x 1, mid 1, r, k)); } inline bool check(int K){ memset(tg, 0, sizeof(tg)); l[0] line(-2 * c[1].l, dp[0] c[1].l * c[1].l); update(1, 1, len, 0); for(int i 1; i n; i){ pi q query(1, 1, len, g(c[i].r 1)); dp[i] (c[i].r 1) * (c[i].r 1) q.first - K; s[i] s[q.second] 1; l[i] line(-2 * c[i 1].l, dp[i] c[i 1].l * c[i 1].l - max((long long)0, (c[i].r - c[i 1].l 1)) * max((long long)0, (c[i].r - c[i 1].l 1))); update(1, 1, len, i); } if(s[n] k) ans dp[n] k * K; return s[n] k; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin n m k; for(int i 1; i n; i){ int x, y; cin x y; x; y; b[i].l min(x, y); b[i].r max(x, y); } sort(b 1, b n 1, cmp); for(int i 1; i n; i){ if(b[i].r c[tot].r){ c[tot] b[i]; a[cnt] c[tot].r 1; } } len unique(a 1, a cnt 1) - a - 1; n tot; int L -1 * m * m, R 0; while(L R){ int mid (L R) 1; if(check(mid)) L mid 1; else R mid - 1; } check(R); cout ans; return 0; }P6047是我最喜欢的丝之歌耶( •̀ ω •́ )y由于只能从左往右切割那么可以注意到对于交叉的两根线切割了左斜的那一条就一定能切割右斜的那一条。即对于题目中的图来说对于左边的两根线来说以上端点从左至右排序第一根线被切了那么第二根也一定会被切掉。由于所有的线都要切所以类似于上图第二根线这样的线完全不用考虑所以可以考虑先把这些线去掉。由于交叉的线都去掉了一根所以去掉之后的图案应该是左端点和右端点都单调递增的那么就可以写出dp式子后面的两个最小值都是可以预处理出来的可以发现其实是一个一次函数用李超线段树维护每次查询查 处的最小值即可。代码#includebits/stdc.h #define int long long using namespace std; const int N 3e5 5; const int M 1e6 5; int n, m, cnt, tot, a[N], b[N], tg[4 * M], ma[N], mb[N], dp[N]; struct line{ int k, b; line(int x 0, int y 0){ k x; b y; } }l[N]; struct silk{ int u, v; }song[N], s[N]; bool cmp(silk x, silk y){ if(x.u y.u) return x.v y.v; return x.u y.u; } void prework(){ sort(song 1, song m 1, cmp); for(int i 1; i m; i){ if(song[i].v s[cnt].v) s[cnt] song[i]; } ma[1] a[1]; for(int i 2; i n; i){ if(a[i] ma[i - 1]) ma[i] a[i]; else ma[i] ma[i - 1]; } mb[n] b[n]; for(int i n - 1; i 1; i--){ if(b[i] mb[i 1]) mb[i] b[i]; else mb[i] mb[i 1]; } l[0].b 1e18; } int f(int x, int id){ return l[id].k * x l[id].b; } void update(int x, int l, int r, int id){ int v tg[x]; int mid (l r) 1; if(f(mid, id) f(mid, v)) swap(id, v); if(f(l, id) f(l, v)) update(2 * x, l, mid, id); if(f(r, id) f(r, v)) update(2 * x 1, mid 1, r, id); } int query(int x, int l, int r, int k){ if(l k || r k) return 1e18; int ans f(k, tg[x]); if(l r) return ans; int mid (l r) 1; return min(ans, min(query(2 * x, l, mid, k), query(2 * x 1, mid 1, r, k))); } signed main(){ cin n m; for(int i 1; i n; i) cin a[i]; for(int i 1; i n; i) cin b[i]; for(int i 1; i m; i) cin song[i].u song[i].v; prework(); for(int i 1; i cnt; i){ l[tot] line(ma[s[i].u - 1], dp[i - 1]); update(1, 0, M, tot); dp[i] query(1, 0, M, mb[s[i].v 1]); } cout dp[cnt]; return 0;