网站动画广告条怎么做的,爱企查企业服务平台,杭州有哪些做网站的公司好,怎么创建一个网址description
“汉中沃野如关中#xff0c;四五百里烟蒙蒙。黄云连天夏麦熟#xff0c;水稻漠漠吹秋风。”——摘自 黄裳《汉中行》 “泉岭精神不朽#xff0c;汉中诸球永生。”——摘自《泉岭精神创立者语录》 “把神犇烤一烤#xff0c;味道会更好。”——摘自《xhr语录》…description
“汉中沃野如关中四五百里烟蒙蒙。黄云连天夏麦熟水稻漠漠吹秋风。”——摘自 黄裳《汉中行》 “泉岭精神不朽汉中诸球永生。”——摘自《泉岭精神创立者语录》 “把神犇烤一烤味道会更好。”——摘自《xhr语录》 “秀恩爱有利于身心健康”——摘自《泉岭精神集大成者语录》 “楼上说的对”——摘自《泉岭精神信徒语录合集》 “不会做积分怎么找妹子”——摘自《xhr语录》 “切实保护耕地以放置更多的哨戒炮。”——摘自《泉岭精神信徒语录合集》 “就算两个包子一起吃掉也不能阻止我修筑梯田。”——摘自《泉岭精神创立者语录》 “我来自泉岭他来自汉中我们半道而逢。”——摘自《泉岭精神集大成者语录》 【问题描述】 作为泉岭精神的缔造者、信奉者、捍卫者、传承者Pear决定印制一些教义问答手册以满足泉岭精神日益增多的信徒。Pear收集了一些有关的诗选、语录其中部分内容摘录在了【题目背景】里。这些语录是按出现的时间排好序的——Pear很喜欢这样的作风于是决定在按时间排好序的基础上选择部分语录制作成若干本教义问答手册。 一共有N条语录。Pear决定从中选出某一段时间内的所有语录在此基础上印制大小为L的若干本教义问答手册。Pear对印制的手册有如下要求 1.每本手册必须包含这个区间内连续的恰好L条语录。 2.不同手册包含的语录不能相同。 3.每条语录有一个“主题相关程度”这个数可正可负。Pear希望所有手册的语录的“主题相关程度”之和尽可能大。 例如对于区间[3,15]和L3一种选择方法是[4,6][9,11][12,14]。这三个区间长度都恰好为L且互不重叠。 Pear并没有决定选哪段时间的语录因此他有Q次询问。每次询问给出两个数[l,r]表示候选语录的范围是第l条到第r条。你能回答出每个询问的最大“主题相关程度”之和么 Input 第一行两个正整数NL含义如上所述。注意对于所有询问L都是一样的。 第二行N个整数绝对值10000。第i个数表示第i条语录的“主题相关程度”。 接下来Q行每行两个正整数l和r表示询问区间。 Output 输出Q行每行表示这组询问的答案。注意这个答案可以是0如果区间负数过于多的话。 Sample Input 15 3 3 1 5 -2 3 -2 -2 2 2 2 0 3 2 -1 0 9 8 10 10 10 9 11 2 14 5 14 5 13 12 13 7 13 2 10
Sample Output 6 0 4 17 11 11 0 11 12 Hint
【数据范围】 对于10%的数据N1000,Q1000,L50 对于另外20%的数据N100000,Q100000,L5 对于另外20%的数据N100000,Q100000,L10 对于100%的数据N100000,Q100000,L50 Source 2014年国家集训队十五人互测
solution
从最原始的O(n2)O(n^2)O(n2)暴力入手 设f[i][j]f[i][j]f[i][j]表示区间[i,j][i,j][i,j]的答案最大值sum[i]sum[i]sum[i]表示前缀和 f[i][j]max(f[i][j−1],f[i][j−L]sum[j]−sum[j−L])f[i][j]max(f[i][j-1],f[i][j-L]sum[j]-sum[j-L])f[i][j]max(f[i][j−1],f[i][j−L]sum[j]−sum[j−L]) 分治分界线midmidmid将[l,r][l,r][l,r]分为左右两个区间
长度为LLL的一段完全属于左区间/右区间跨越了midmidmid在左右区间都有的一段
第一种完全属于某半边区间的就直接分治递归处理 考虑第二种情况对每一个l′ll′预处理出在[l′,mid][l,mid][l′,mid]区间选了若干个长度为LLL的区间且在末尾选了xxx个数的最大值然后对每一个r′rr′预处理出在[mid1,r‘’][mid1,r‘’][mid1,r‘’]区间选了若干个长度为LLL的区间并在开头选了xxx个数的最大值
fl[i][j]fl[i][j]fl[i][j]以jjj为左端点左区间末尾选了iii个数的最大值 fr[i][j]fr[i][j]fr[i][j]以jjj为右端点右区间开头选了iii个数的最大值
最后询问可以整体二分一并处理
思路好懂主要是代码细节很ex人
code
#include cstdio
#include iostream
using namespace std;
#define maxn 100005
int n, L, Q;
int p[maxn], ql[maxn], qr[maxn], sum[maxn];//前缀和差分
int fl[55][maxn], fr[55][maxn];
int Left[maxn], Right[maxn], ans[maxn];
//fl[i][j]:以j为左端点 在末尾选了i个数 的最大值
//fr[i][j]:以j为右端点 在开头选了i个数 的最大值
//预处理时的最大值只加了完整L的区间值
void calc_L( int l, int r ) {//对左区间进行预处理 for( int i 0;i min( r - l 1, L );i ) {//枚举跨越mid的在区间末尾选的长度i fl[i][r - i 1] 0;for( int j r - i;j l;j -- )//枚举区间的左端点jfl[i][j] j L - 1 r - i ? 0 : max( fl[i][j 1], fl[i][j L] sum[j L - 1] - sum[j - 1] );//r-i就是不与枚举末尾长度i的起始点相交的第一个点//换言之[r-i1,r]就是枚举的一个跨越mid的L区间在左半边的部分 //三目运算符判断是否以j为左端点时可以划分出一个完整的在区间的L且不交 (j~jL-1)}
}
/*
fl[L]一个跨越mid的长度L区间在左半边就有L个 也就相当于压根没跨越
fr[L]同理也相当于压根没跨越
此情况恰好与fl[0],fr[0]差了一个L的区间划分循环
故可以由fl[0],fr[0]表示
*/
void calc_R( int l, int r ) {for( int i 0;i min( r - l 1, L );i ) {fr[i][l i - 1] 0;//[l,li-1]就是枚举的一个跨越mid的L划分区间在右半边的部分 for( int j l i;j r;j )fr[i][j] j - L 1 l i ? 0 : max( fr[i][j - 1], fr[i][j - L] sum[j] - sum[j - L] );//三目运算符判断是否以j为右端点时可以划分出一个完整的在区间的L且不交 (j-L1~j)}
}void solve( int Ql, int Qr, int l, int r ) {if( Ql Qr || r - l 1 L ) return;int mid ( l r ) 1;int lenl 0, lenr 0;calc_L( l, mid );calc_R( mid 1, r );for( int i Ql;i Qr;i ) {int id p[i];if( qr[id] mid ) Left[ lenl] id;else if( ql[id] mid ) Right[ lenr] id;else {ans[id] fl[0][ql[id]] fr[0][qr[id]];//不存在跨越mid的L区间的情况下 最大值//dp动态规划预处理已经做到局部最优解for( int j max( 1, L - ( qr[id] - mid ) );j mid - ql[id] 1 j L;j )ans[id] max( ans[id], ( mid - j l ? 0 : fl[j][ql[id]] ) ( mid L - j 1 r ? 0 : fr[L - j][qr[id]] ) sum[mid L - j] - sum[mid - j] );/*mid-j mid1L-j都是两边不相交的第一个点ps:注意括号问题 要把三目运算符整个括在一起 不然会错该跨越mid的区间应为 mid-j1 ~ mid1 L-j - 1 枚举跨越mid的L区间的左区间长度jmax(1,L-(qr[id]-mid))保证至少要有1个 且 该区间的右端点抵到整个询问区间的右端点qr[id]mid-ql[id]1jL保证至多有L-1个这样右边才至少有一个 且 该区间的最多只能抵到整个询问区间的左端点ql[id]判断一下mid-jl没有因为只预处理了左端点l的其余部分应该全为0同理右边判断一下midL-j1r没有只处理了右端点r其余部分应该全为0然后加上跨越的长度为L的区间的a值和但是好像去掉判断也是AC的不懂了 按道理不能去掉的啊ans[id] max( ans[id], fl[j][ql[id]] fr[L - j][qr[id]] sum[mid L - j] - sum[mid - j 1 - 1] );*/}}for( int i 1;i lenl;i ) p[Ql i - 1] Left[i];for( int i 1;i lenr;i ) p[Ql lenl i - 1] Right[i];solve( Ql, Ql lenl - 1, l, mid );solve( Ql lenl, Ql lenl lenr - 1, mid 1, r );//注意这里不再是solve(Qllenl,Qr,mid1,r); 进行分类后有一些询问操作是已经处理了的
}int main() {scanf( %d %d, n, L );for( int i 1;i n;i ) {scanf( %d, sum[i] );sum[i] sum[i - 1];}scanf( %d, Q );for( int i 1;i Q;i ) {p[i] i;scanf( %d %d, ql[i], qr[i] );}solve( 1, Q, 1, n );for( int i 1;i Q;i )printf( %d\n, ans[i] );return 0;
}
//代码参考博客https://www.cnblogs.com/Orz-IE/p/12039213.html
