快餐店[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教授要求: 在一个一维容器中的玩具编号是连续的。 同时如果一个一维容器中有多个玩具,那么两件玩具之间要加...

逃亡「GDOI2017」

【题目描述】兔兔和蛋蛋是一对cp,她们的国家目前正发生战乱,所以她们正在决定是否一起逃离这个国家。 该国家有$n$个城市,城市之间的道路形成一棵有向树。只能从父节点城市走到子节点城市。$1$号城市是首都,从城市$1$可以到达所有城市。每个城市都有一支军队,编号为$i$的城市其军队的攻击力为$b_i$,如果城市$i$能到达城市$j$,且$b_i > b_j$(城市 i 军队的攻击力大于城...

领导集团问题「FJOI2018」

【题目描述】一个公司的组织领导架构可以用一棵领导树来表示。公司的每个成员对应于树中一个结点$v_i$,且每个成员都有响应的级别$w_i$。越高层的领导,其级别值$w_i$越小。树中任何两个结点之间有边相连,则表示与结点相应的两个成员属于同一部门。领导集团问题就是根据公司的领导树确定公司的最大部门。换句话说,也就是在领导树中寻找最大的部门结点子集,使得的结点$v_i$和$v_j$,如果$v_i...

逆序对[AHOI2008]

【题目描述】小可可和小卡卡想到Y岛上旅游,但是他们不知道Y岛有多远。好在,他们找到一本古老的书,上面是这样说的: 下面是$N$个正整数,每个都在$1\sim K$之间。如果有两个数$A$和$B$,$A$在$B$左边且$A$大于$B$,我们就称这两个数为一个“逆序对”。你数一数下面的数字里有多少个逆序对,你就知道Y岛离这里的距离是多少千米了。 比如说,$4,2,1,3,3$里面包含了$5$个逆...

逆序对数列[HAOI2009]

【题目描述】对于一个数列$a$,如果有$a_i>a_j$且$i<j$,那么我们称$a_i$与$a_j$为一对逆序对数。若对于任意一个由$1\sim n$自然数组成的数列,可以很容易求出有多少个逆序对数。那么逆序对数为$k$的这样自然数数列到底有多少个? 【输入格式】第一行为两个整数$n,k$。 【输出格式】写入一个整数,表示符合条件的数列个数,由于这个数可能很大,你只需输出该数对...