资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

codeforces455E-创新互联

题目：http://codeforces.com/problemset/problem/455/Ecodeforces455E

题意：给定数组a，及f的定义：

成都创新互联专注于治多企业网站建设,自适应网站建设,成都做商城网站。治多网站建设公司,为治多等地区提供建站服务。全流程按需网站开发，专业设计，全程项目跟踪，成都创新互联专业和态度为您提供的服务

    f[1][j] = a[j];  1 <= j <= n

    f[i][j] = min(f[i-1][j-1], f[i-1][j]) + a[j];  2 <= i <= j <= n

 给定q个询问，每个询问为l,r,求f[l][r]

My solution:

 写一些小数据就可以发现，其实对于一个询问l,r,其实等价于：

       从[r-l+1, r]这个区间内取l个数，使其和最小。但是比较特殊的是，一个数可以取多次，并且如果取了一个x，那么[x+1,r]间的所有数必须得取。

       例如，对于n=3， a = {2, 1, 3}

       询问l=3, r=3的取法有：3+3+3=9， 3+3+1=7, 3+1+1=5, 3+1+2= 6；答案为3+1+1=5

   2.设答案f[l][r]的询问答案合法区间是在[x, r]这一段取得的，我们还可以发现如下的性质：

     1)a[x]一定是[x,r]中最小的，否则存在 x<=y<=r, a[y] <= a[x],比[x,r]更优的区间[y, r]

       除[y, r]的共同区间外，剩下的l-y-r个[y,r]区间可以全取a[y]，显然比[x,r]更小

     2)a[x+1]~a[y]各取一个，剩下的全取a[x]，因为a[x]是区间最小元素，取越多答案越小

   3.基于2我们可以维护一个递增的序列来求答案，但是这样还是不够，妥妥TlE

    只能看下决策之间有什么关系了；

    对于询问（l,r)不妨设两个决策k

    那么 (sum[r] - sum[k]) - (l - (r - k)) * a[k] <= (sum[r] - sum[j]) - (l - (r - j)) * a[j];

    整理一下式子：

         (sum[k] - a[k]*k) - (sum[j] - a[j]*j) / (a[k] - a[j]) <= l - r;

    这不就是个斜率的式子，剩下的就是维护一个凸壳即可

    4.具体的话对于询问按照r排序，然后离线做

      然后二分一左边界，找到合法区间完，再二分找到合法的斜率。具体看代码吧

code：

 1 #include 
 2 #include 
 3 #include 
 4 #include 
 5 #include 
 6 #include 
 7 #include 
 8 #include 
 9 #include 
10 #include 
11 #include 
12 #include 
13 #include 
14 #include 
15 #include 
16 #include 
17 #include 
18 #include 
19 #include 
20 #include 
21 #define M0(x) memset(x, 0, sizeof(x))
22 #define pb push_back
23 #define mp make_pair
24 #define x first
25 #define y second
26 #define vii vector< pair >::iterator 
27 using namespace std;
28 const int maxn = 100010;
29 vector< pair > ask[maxn];
30 int n, m;
31 long long sum[maxn], ans[maxn];
32 int s[maxn], top, a[maxn];
33 
34 inline double slope(int k, int j){
35  double yk = sum[k] - (double)k * a[k], yj = sum[j] - (double)j * a[j];
36  return (yk - yj) / (a[k] - a[j]);
37 }
38 
39 void init(){
40   for (int i = 1; i <= n; ++i)
41         scanf("%d", a+i), sum[i] = sum[i-1] + a[i];
42   for (int i = 0; i <= n; ++i) ask[i].clear();
43     scanf("%d", &m);
44   int l, r;
45   for (int i = 0; i < m; ++i){
46          scanf("%d%d", &l, &r);
47          ask[r].pb(mp(l, i));
48     }
49 }
50 
51 void solve(){
52   int top = 0;
53   int l, r, mid, pos;
54   for (int i = 1; i <= n; ++i){
55   while (top > 0 && a[s[top]] >= a[i]) --top;
56   while (top > 1 && slope(s[top], i) >= slope(s[top-1], i)) --top;
57           s[++top] = i;
58   for (vii it = ask[i].begin(); it != ask[i].end(); ++it){
59                 l = lower_bound(s+1, s+top+1, i-it->x+1) - s;
60                 r = top-1, pos = i;
61   while (l <= r){
62                       mid = (l + r) >> 1;
63   if (slope(s[mid], s[mid+1]) <= it->x - i) pos = s[mid], r = mid - 1;
64   else l = mid + 1;
65                 }
66                 ans[it->y] = sum[i] - sum[pos] + (long long)a[pos]*(it->x+pos-i);
67           }    
68     }
69   for (int i = 0; i < m; ++i)
70        printf("%I64d
", ans[i]); 
71 }
72 int main(){
73 //    freopen("a.in","r",stdin);
74 //    freopen("a.out","w",stdout);75   while (scanf("%d", &n) != EOF){
76         init();
77         solve();
78     }
79   return 0;
80 }
View Code


当前标题：codeforces455E-创新互联
标题路径：http://cdkjz.cn/article/jsdog.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
成都搬家公司雅安机房托管开元建校成都广告制作定制网站设计工商财税新网创想网站改版维护App开发H5网站制作

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图