发布于

HDU – 6133 启发式合并

题意:给出一棵树共$n$个顶点,每个顶点有一个权值$val_i$,你需要对每个节点统计一个最优解, 每个节点的解按照一定规则产生:取出该节点的子树下所有的顶点,把顶点任意排序成一个序列,设为$v_1,v_2...,v_k$, 此时解为$\sum_{i=1}^{k}\sum_{j=1}^{i}val_{v_j}$,最小的解为最优解 （更多…）
发布于

ZOJ – 3649 树上倍增

题意:给出一个图,先求出最大生成树,然后多次询问树上路径$u→v$的有向最大极差$max(a_i-a_j),i>j$,其中$i$和$j$指代节点在路径中出现的顺序 （更多…）
发布于

POJ – 1821 单调队列优化DP

题意:n个墙壁m个粉刷匠,每个墙壁至多能被刷一次,每个粉刷匠要么不刷,要么就粉刷包含第Si块的长度不超过Li的连续墙壁(中间可不刷),每一块被刷的墙壁都可获得Pi的利润,求最大利润 （更多…）
发布于

HDU – 4866 主席树 二分

题意:在x轴$[1,X]$内的上空分布有n个占据空间$[L_i,R_i]$,高度$D_i$的线段,射中线段的得分为其高度,每次询问从x轴的$x$往上空射的最近k个线段的总得分,具体得分制看题 （更多…）
发布于

51nod – 1163 巧妙的并查集 O(1)维护区间

题意:有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。 （更多…）
发布于

CodeChef – RIN 最小割应用 规划问题

题意：给定$n$门课和$m$个学期，每门课在每个学期有不同的得分，需要选定一个学期去完成，但存在约束条件，共有$k$对课程需要$a$在$b$开始学前学会，求最大得分（原问题是求最高平均得分） （更多…）