最佳团体[JSOI2016]

https://www.luogu.com.cn/problem/P4322 题解网上怎么这么多O(n^3\log n)假做法啊。。。一条链就卡掉了 假设0号节点是根 建出表示依赖关系的图 发现正好有n条边且每个点的父亲都比它编号小所以正好是一棵树 那么原问题就是要在树上取一个包含根的性价比最高的连通块 看到”性价比”考虑使用01分数规划 假设x_i\in \{0,1\}表示第i个人选不选 ...

无归岛[HNOI2009]

题目描述https://www.luogu.com.cn/problem/P4410 题解原图显然是一个仙人掌(似乎还有些别的性质 但是其实没什么必要) 先考虑树的情况,题意即为不能同时选择相邻的两点,设f[x][0/1]表示选/不选x时,x子树内的最大战斗力 f[x][0]=\max\limits_{y\in son(x)} (\max(f[y][0],f[y][1]))f[x][1]=\...

仓库建设[ZJOI2007]

题目描述https://www.luogu.com.cn/problem/P2120 题解设S_i=\sum\limits_{j=1}^{i} p_j,T_i=\sum\limits_{j=1}^{i} p_j*a_j $S_i$即为前i个工厂的物品总数,T_i为前i个工厂都把所有物品运到工厂1的总花费(虽然不能运到仓库1) 设f_i表示把前i个工厂的物品都运到仓库里且在i工厂处建立仓库的...

征途[SDOI2016]

题目描述Pine 开始了从S地到T地的征途。 从S地到T地的路可以划分成h段,相邻两段路的分界点设有休息站。Pine 计划用m天到达T地。除第n天外,每一天晚上 Pine 都必须在休息站过夜。所以,一段路必须在同一天中走完。Pine 希望每一天走的路长度尽可能相近,所以他希望每一天走的路的长度的方差尽可能小。 帮助 Pine 求出最小方差是多少。 设方差是v,可以证明,v*m^2是一个整数。...

快餐店[NOI2013]

题目描述小 T 打算在城市 C 开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的,小 T 希望快餐店的地址选在离最远的顾客距离最近的地方。 快餐店的顾客分布在城市 C 的N个建筑中,这N个建筑通过恰好N条双向道路连接起来,不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小 T 的快餐店可以开设在任一建筑中,也可...

方伯伯的玉米田[SCOI2014]

题目描述方伯伯在自己的农田边散步,他突然发现田里的一排玉米非常的不美。这排玉米一共有$N$株,它们的高度参差不齐。方伯伯认为单调不下降序列很美,所以他决定先把一些玉米拔高,再把破坏美感的玉米拔除掉,使得剩下的玉米的高度构成一个单调不下降序列。方伯伯可以选择一个区间,把这个区间的玉米全部拔高$1$单位高度,他可以进行最多$K$次这样的操作。拔玉米则可以随意选择一个集合的玉米拔掉。问能最多剩多少...

分零食[JSOI2012]

题目描述题面太长有$n$个人,$m$颗糖,要求给前若干个人分糖(把所有糖分完),如果一个人得到了$x$颗糖,那他的欢乐度就是$Ox^2+Sx+U$,一个分糖方案的总欢乐度是所有分到糖的人的欢乐度的乘积,求所有可行分糖方案的总欢乐度的总和。 题解首先有一个显然的dp方程: 设$dp[i][j]$表示给前$i$个人分了$j$颗糖,设$f(x)=Ox^2+Sx+U$,则$dp[i][j]=\sum...

移动金币「SDOI2019」

题目描述一个$1\times n$的棋盘上最初摆放有$m$枚金币。其中每一枚金币占据了一个独立的格子,任意一个格子内最多只有一枚金币。 Alice 和 Bob 将要进行如下的一场游戏。二人轮流操作,且 Alice 先行。当轮到一个玩家的时候,他可以选择一枚金币,并将其向左移动任意多格,且至少移动一格。金币不能被移出棋盘,也不能越过其它金币。 如果轮到一个玩家的时候他已经无法做出任何有效操作了...

串珠子[BZOJ2560]

题目描述铭铭有$n$个十分漂亮的珠子和若干根颜色不同的绳子。现在铭铭想用绳子把所有的珠子连成一个整体。 现在已知所有的珠子互不相同,用整数$1$到$n$编号。对于第$i$个珠子和第$j$个珠子,可以选择不用绳子连接,或者在$c_{i,j}$根不同颜色的绳子中选择一根将它们连接。如果把珠子看作点,把绳子看作边,将所有珠子连成一个整体即为所有点构成一个连通图。特别地,珠子不能和自己连接。 铭铭希...

玩具装箱[HNOI2008]

题目描述P 教授要去看奥运,但是他舍不下他的玩具,于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩,其可以将任意物品变成一堆,再放到一种特殊的一维容器中。 P 教授有编号为$1 \cdots n$的$n$件玩具,第$i$件玩具经过压缩后的一维长度为$C_i$。 为了方便整理,P教授要求: 在一个一维容器中的玩具编号是连续的。 同时如果一个一维容器中有多个玩具,那么两件玩具之间要加...