分类 - 动态规划

? 解题记录 ? ? 洛谷 ? ? 博弈论 ? ? 动态规划 ? ? 搜索 ?    2019-01-30 17:26:26    864    0    0
题目描述菲菲和牛牛在一块n 行m 列的棋盘上下棋,菲菲执黑棋先手,牛牛执白棋后手。 棋局开始时,棋盘上没有任何棋子,两人轮流在格子上落子,直到填满棋盘时结束。 落子的规则是:一个格子可以落子当且仅当这个格子内没有棋子且这个格子的左侧及上方的所有格子内都有棋子。 棋盘的每个格子上,都写有两个非负整数,从上到下第i 行中从左到右第j 列的格 子上的两个整数记作Ai,j​ 、Bi,j​ 。在游戏结束后,菲菲和牛牛会分别计算自己的得分:菲菲的得分是所有有黑棋的格子上的Ai,j​ 之和,牛牛的得分是所有有白棋的格子上的Bi,j​的和。 菲菲和牛牛都希望,自己的得分减去对方的
? 解题记录 ? ? BZOJ ? ? 动态规划 ?    2018-12-19 11:55:14    339    0    0
【题目描述】IOI铁路是由N+2个站点构成的直线线路。这条线路的车站从某一端的车站开始顺次标号为0...N+1。 这条路线上行驶的电车分为上行电车和下行电车两种,上行电车沿编号增大方向行驶,下行电车沿编号减小方向行驶。乘坐这两种电车的话,移动1站的距离需要T秒。换句话说,乘坐上行电车从车站i走到车站i+1需要T秒,称作下行电车从车站i走到车站i-1也需要T秒。你不能在0号车站乘坐下行电车,或在N+1号车站乘坐上行电车。由于电车发车的频率非常高,你可以无视等待电车消耗的时间。 每个车站设有上行电车的站台和下行电车的站台,连接两个站台的道路上设有邮戳台。 现在,IOI铁路召开了邮戳拉力赛。在拉力赛
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 状态压缩 ?    2018-12-13 08:35:48    738    0    0
传送魔法:biu~~~~~~~ 算是一道较有趣的dp" role="presentation" style="position: relative;">dpdpdp了。 首先有一个简单的做法,状压3" role="presentation" style="position: relative;">333进制。 第i" role="presentation" style="position: relative;">iii位是0" role="presentation" style="position: relative;">000表示ai" role="pres
? 解题记录 ? ? LOJ ? ? FMT|FWT ? ? 动态规划 ? ? 状态压缩 ?    2018-12-10 09:19:13    389    0    0
题目地址:嘤嘤嘤 听说是FMT" role="presentation" style="position: relative;">FMTFMTFMT裸题然而学了FMT" role="presentation" style="position: relative;">FMTFMTFMT还是不会啊QAQ" role="presentation" style="position: relative;">QAQQAQQAQ。 首先有一个比较显然的dp" role="presentation" style="position: relative;">dpdpdp。
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 期望概率 ? ? 状态压缩 ? ? FMT|FWT ?    2018-12-05 21:25:10    852    0    0
链接:戳轻点 >_< 神仙题啊! 还不自量力的想了半天。 看完题解发现自己更本没资格做这道题…… 首先貌似有个没分的高斯消元? 嗯……全部都至少走一遍的期望根本不会算啊。 我们先来看一个很好理解的结论: 最值反演:   考虑任意集合S" role="presentation" style="position: relative;">SSS,元素i" role="presentation" style="position: relative;">iii有点权wi" role="presentation" style="position: r
? 解题记录 ? ? LOJ ? ? 动态规划 ? ? 状态压缩 ? ? 组合数 ?    2018-12-05 20:33:53    851    0    0
题目地址:呀,戳轻点qwq 一开始自己就想错了,本来以为只要选择的点集定了,那么覆盖状态也就定了。 但是发现并不对,和点选择的顺序还有关。 …… 我们去Orz" role="presentation" style="position: relative;">OrzOrzOrz题解吧。 发现自己仍然是没有完全理解增量的构造方式。 考虑到选择点的顺序其实是和答案有关的,我们考虑对整个操作序列增量的过程进行dp" role="presentation" style="position: relative;">dpdpdp。 设f(i,S)" role="presenta
? 解题记录 ? ? HDU ? ? 动态规划 ? ? FMT|FWT ?    2018-11-25 17:13:36    554    0    0
Problem Description Byteasar has a tree T with n vertices conveniently labeled with 1,2,...,n. Each vertex of the tree has an integer value vi.The value of a non-empty tree T is equal to v1⊕v2⊕...⊕vn, where ⊕ denotes bitwise-xor.Now for every in
? 解题记录 ? ? BZOJ ? ? 斜率优化 ? ? 带权二分 ? ? 动态规划 ?    2018-11-04 16:21:53    718    0    0
【题目描述】 小H最近迷上了一个分隔序列的游戏。在这个游戏里,小H需要将一个长度为n的非负整数序列分割成k+1个非空的子序列。为了得到k+1个子序列,小H需要重复k次以下的步骤: 1.小H首先选择一个长度超过1的序列(一开始小H只有一个长度为n的序列——也就是一开始得到的整个序列); 2.选择一个位置,并通过这个位置将这个序列分割成连续的两个非空的新序列。 每次进行上述步骤之后,小H将会得到一定的分数。这个分数为两个新序列中元素和的乘积。小H希望选择一种最佳的分割方式,使得k轮之后,小H的总得分最大。 【输入】 输入第一行包含两个整数n,k(k+1≤n)。 第二行包含n
? 解题记录 ? ? 洛谷 ? ? 动态规划 ? ? 斜率优化 ? ? 凸包 ? ? stl ?    2018-11-04 15:44:33    661    0    0
Description 小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和 B纪念券(以下 简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动, 两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的 价值分别为 AK 和 BK(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法 。比例交易法分为两个方面:(a)卖出金券:顾客提供一个 [0,100] 内的实数 OP 作为卖出比例,其意义为:将  OP%
? 解题记录 ? ? 洛谷 ? ? 动态规划 ?    2018-11-04 15:12:50    541    0    0
题目描述今天是hidadz小朋友的生日,她邀请了许多朋友来参加她的生日party。 hidadz带着朋友们来到花园中,打算坐成一排玩游戏。为了游戏不至于无聊,就座的方案应满足如下条件: 对于任意连续的一段,男孩与女孩的数目之差不超过k。 很快,小朋友便找到了一种方案坐了下来开始游戏。hidadz的好朋友Susie发现,这样的就座方案其实是很多的,所以大家很快就找到了一种,那么到底有多少种呢?热爱数学的hidadz和她的朋友们开始思考这个问题…… 假设参加party的人中共有n个男孩与m个女孩,你是否能解答Susie和hidadz的疑问呢?由于这个数目可能很多,他们只想知道这个数目除以12345