首页 > 代码库 > Codeforces Round #260(Div. 1)E
Codeforces Round #260(Div. 1)E
纪念自己过的第一道CF Div.1的E题，不过好多的地方都有点的不太理解，差不多可以说是照着比人的代码打了一遍，以后有空自己再写一遍......
首先，把题目转化为一个贪心问题：对于每个询问(x, y)，发现在
- f(1, j) = a[j], 1 ≤ j ≤ n.
- f(i, j) = min(f(i - 1, j), f(i - 1, j - 1)) + a[j], 2 ≤ i ≤ n, i ≤ j ≤ n.
这两个条件中，可以想象一下，从y, y走到1, l的某个位置，而且路径上y坐标不会增加，而且l是[l,y]中最小的那个数，代价就为sum[y] - sum[l] + a[l]·(x - y + l)
最小的那个点肯定要尽可能多用
于是一顿乱推得到一个 sum[y] + a[l]·(x - y) + a[l]·l - sum[l]， 令k = a[l], X = x - y, b = a[l] * l - sum[l]，发现和y = k * x + b很像，于是就可以依靠这个来解决问题了
期中sum[y]在那个式子里面可有可无，所以可以单独提出来
然后就是靠线段树来维护一个凸包，为什么要用凸包呢？为什么要会线段树呢？
如果你求出了一个下凸包(其实感觉有点像半平面交),对于一个点x，凸包上的直线满足一个很好的性质，就是这些线是按k排序的，于是就可以二分
怎么维护呢？类似于归并排序的方法，不过为了方便询问就利用了线段树
代码
1 #include <set> 2 #include <map> 3 #include <queue> 4 #include <deque> 5 #include <cmath> 6 #include <vector> 7 #include <string> 8 #include <cstdio> 9 #include <cstdlib> 10 #include <cstring> 11 #include <cassert> 12 #include <iostream> 13 #include <algorithm> 14 15 using namespace std; 16 17 typedef long long LL; 18 typedef pair <int, int> PII; 19 20 const int N = 1e5 + 7; 21 const int INF = 0x3f3f3f3f; 22 const int MOD = 1e9 + 7; 23 const double EPS = 1e-6; 24 const double PI = acos(-1.0); 25 26 int data[N], sum[N]; 27 28 struct ConvexHull{ 29 vector <int> k, b; 30 void clear(){ 31 k.clear(); 32 b.clear(); 33 } 34 double Intersect(int k1, int b1, int k2, int b2){ 35 return (double)(b2 - b1) / (k1 - k2); 36 } 37 void push(int kk, int bb){ 38 int n = k.size(); 39 while (n > 1 && ((k.back() == kk && b.back() > bb) || (k.back() != kk && 40 Intersect(k[n - 1], b[n - 1], k[n - 2], b[n - 2]) > Intersect(k[n - 1], b[n - 1], kk, bb)))){ 41 --n; 42 k.pop_back(); 43 b.pop_back(); 44 } 45 while (n && k.back() == kk && b.back() > bb){ 46 --n; 47 k.pop_back(); 48 b.pop_back(); 49 } 50 if (n && k.back() == kk && b.back() <= bb){ 51 return; 52 } 53 k.push_back(kk); 54 b.push_back(bb); 55 } 56 int get(int x){ 57 // printf("Calc %d\n", x); 58 // int res = INF; 59 // for (int i = 0; i < k.size(); ++i){ 60 // res = min(); 61 // } 62 int l = 0, r = k.size() - 1, mid; 63 while (l < r){ 64 mid = (l + r) >> 1; 65 if (k[mid] * x + b[mid] < k[mid + 1] * x + b[mid + 1]) 66 r = mid; 67 else 68 l = mid + 1; 69 } 70 return k[l] * x + b[l]; 71 } 72 void debug(){ 73 for (int i = 0; i < k.size(); ++i) 74 printf("%d %d\n", k[i], b[i]); 75 } 76 }; 77 78 struct Node{ 79 int a, b; 80 ConvexHull g; 81 Node *l, *r; 82 }; 83 84 struct SegmentTree{ 85 Node tree[N << 1], *root; 86 int pos; 87 88 void merge(ConvexHull &res, const ConvexHull &a, const ConvexHull & b){ 89 res.clear(); 90 int p1 = 0, p2 = 0; 91 while (p1 < a.k.size() && p2 < b.k.size()){ 92 if (a.k[p1] > b.k[p2]){ 93 res.push(a.k[p1], a.b[p1]); 94 ++p1; 95 } else { 96 res.push(b.k[p2], b.b[p2]); 97 ++p2; 98 } 99 }100 while (p1 < a.k.size()){101 res.push(a.k[p1], a.b[p1]);102 ++p1;103 }104 while (p2 < b.k.size()){105 res.push(b.k[p2], b.b[p2]);106 ++p2;107 }108 }109 110 Node *build(int a, int b){111 Node *root = &tree[++pos];112 root->a = a;113 root->b = b;114 if (a == b){115 root->g.clear();116 root->g.push(data[a], data[a] * a - sum[a]);117 return root;118 }119 int mid = (a + b) >> 1;120 root->l = build(a, mid);121 root->r = build(mid + 1, b);122 // printf("Merge : [%d - %d]\n", a, b);123 // printf("A : \n");124 // root->l->g.debug();125 // printf("B : \n");126 // root->r->g.debug();127 merge(root->g, root->l->g, root->r->g);128 // printf("Res : \n");129 // root->g.debug();130 return root;131 }132 133 void init(int n){134 pos = 0;135 root = build(1, n);136 }137 138 int find(Node *root, int a, int b, int x){139 if (a <= root->a && root->b <= b){140 return root->g.get(x);141 }142 int mid = (root->a + root->b) >> 1, res = 0;143 if (a <= mid)144 res = min(res, find(root->l, a, b, x));145 if (b > mid)146 res = min(res, find(root->r, a, b, x));147 return res;148 }149 150 int query(int x, int y){151 return find(root, y - x + 1, y, x - y);152 }153 }tree;154 155 int main(void){156 freopen("a.in", "r", stdin)157 freopen("a.out", "w", stdout);158 int n;159 scanf("%d", &n);160 for (int i = 1; i <= n; ++i){161 scanf("%d", &data[i]);162 sum[i] = sum[i - 1] + data[i];163 }164 tree.init(n);165 int Q, x, y;166 scanf("%d", &Q);167 while (Q--){168 scanf("%d%d", &x, &y);169 printf("%d\n", sum[y] + tree.query(x, y));170 }171 return 0;172 }
Codeforces Round #260(Div. 1)E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。