从品牌网站建设到网络营销策划,从策略到执行的一站式服务
题意:给定数组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:
View Code 1 #include
12 #include
名称栏目:codeforces455E-创新互联
URL地址:http://www.cdkjz.cn/article/jsdog.html
成都网站建设公司地址:成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220
成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.
专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网! | 成都网站建设哪家好? | 网站建设地图