Category Archives: 优化问题

HDU 5749 Colmerauer (乱搞)

Peter有一个n×m的矩阵M. 定义S(a,b)为M的所有大小为a×b的子矩阵的权值和. 一个矩阵的权值是这 …

FZU 2178 礼物分配 (二分)

给出n(<=30)个物品,A选择每件物品都有他对应的权值vi,B选择每件物品都有他对应的权值wi,两个人 …

CSU A Simple Problem (单调队列)

给出n个数字, 求一段最长的连续区间, 使得区间最大值-最小值不超过k. 题目链接: here 用l, r维护 …

Codeforces 653 E Bear and Forgotten Tree 2 (分析)

给出一个菊花图,有n个点,然后给出m个信息表示某两个点之间没有边,也就是说这个图的边数非常多——菊花图。判断这 …

codeforces 660 F Bear and Bowling 4 (分析,三分)

给出一个数列,然后计算最大的sum[l, r] = a[l] * 1 + a[l + 1] * 2 + &#8 …

POJ 3415 Common Substrings (后缀数组,单调栈优化)

给出两个串,定义f(i, j, k)表示A[i…..i + k – 1] = B[j& …

SGU 148 B-Station (大根堆)

一个n层的建筑,每层都有积水,可以用炸药炸掉这层但是要花费,那么水就会流到下一层,如果某层积水大于能够承载的容 …

Codeforces 578C Weakness and Poorness (三分,最大连续子序列)

题意:给出一个数列,求出某个x使得绝对值最大连续子序列最小. 题解:三分x,然后去判断逼近解,判断直接dp就好 …

HDU 5425 Rikka with Tree II (概率)

题意:一棵树,现在从树上任意选择至少两个点的方案数 2 ^ n – n – 1, 那么 …

hdu 5371 Hotaru’s problem (manacher,set维护)

题意:找出满足这样性质的最长子串:子串类似wbw的形式,w和b构成回文。 题解:对已每个位置,以他为中心的最长 …