AFreeMan

分类

BFS(1) CDQ分治和整体二分(1) Codeforces(15) DFS(4) GDUT训练(8) KMP(1) MST(1) RMQ(2) Trie(1) 二分(3) 几何(2) 区间型DP(5) 单调栈(3) 容斥原理(2) 尺取(1) 差分(1) 广工新生赛题解(1) 序列型DP(1) 思维(1) 拓扑排序(1) 排序(3) 搜索(2) 数位DP(5) 数论(9) 无向图双连通分量(1) 最短路(8) 未归档(95) 杂(5) 栈/(优先)队列/链表(1) 树形DP(2) 树链剖分(2) 棋盘型DP(4) 概率/期望DP(3) 模拟退火(1) 物理(1) 状压型DP(9) 矩阵快速幂(2) 线性DP(4) 线段树/树状数组(8) 组合数学(1) 缩点(不仅SCC)(1) 网络流(4) 背包型DP(4) 莫队算法(2) 贪心(3) 题解(3)

/ 注册

全部文章（共238篇）

洛谷P1005 矩阵取数游戏

最先很自然地想到贪心，而且确信贪心是对的，实际上太坑了，肯定是错的。反例：10,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,8,8,8,8,8,9对于这个序列，按照贪心，先取右边的，最后取10，这样的话这么多大的8就被很小的幂浪费了，先取10的话，后面的8都被高效地利用了...

2018-12-22

0 393

洛谷P1004 方格取数 & P1006 传纸条

P1004 方格取数https://www.luogu.org/problemnew/show/P1004 P1006 传纸条https://www.luogu.org/problemnew/show/P1006 方格取数：设f(i,j,k,l)为从原点分别走两条路径分别到(i,j),...

2018-12-22

0 504

洛谷P1417 烹调方案

https://www.luogu.org/problemnew/show/P1417 这道题不同于普通的01背包，不同的先选择的做菜策略会对之后产生不同的影响，即不满足“无后效性”。但是，考虑一种选择策略，假设有两个先后做的菜i和j，交换他们的顺序会产生什么影响呢？假设ij之前的时间为t ...

2018-12-21

0 328

洛谷P1736 创意吃鱼法

https://www.luogu.org/problemnew/show/P1736 开始自己想：设f(i,j):以（i，j）为左上角的包含（i，j）的最大子正方形大小，则f(i,j)取决于：设t=f(i+1,j+1)，（i，j）右以及下方的t个元素最多连续几个0，可以用二分+前缀和。我只会lo...

2018-12-20

0 449

洛谷P1387 最大正方形

https://www.luogu.org/problemnew/show/P1387 开始自己想的：设f(i,j):以（i，j）为左上角的包含（i，j）的最大子正方形大小，则f(i,j)取决于：设t=f(i+1,j+1)，（i，j）右以及下方的t个元素最多连续几个1。由于只有01，所以用前缀和+...

2018-12-20

0 565

洛谷P1282 多米诺骨牌

每个骨牌上下相差最多为6-1=5，1000个骨牌最多相差5000，考虑正负，偏移5000，可以开10000大小的数组存上下差值设f(i,j)：前i个骨牌，上比下多j-5000个对应的最少旋转次数。 f(0,5000)=0,f(0,j)=inf f(i,j)=min{f(i-1,j-(a[i]...

2018-12-19

0 342

洛谷P1880 [NOI1995]石子合并

设f(i,j)表示第i堆到第j堆合并的总最大得分，f(i,j)=max{f(i,k)+f(k+1,j)+sum[i~j]} 由于是环形的，n的环写成2*n的链，环的最优值等于n条以不同点为起点的链的最优值之中最优的那一个。如123456->123456123456，然后dp就可以轻易做分...

2018-12-19

0 392

洛谷 P1140 相似基因

https://www.luogu.org/problemnew/show/P1140 根据题目给出的碱基配对表，发现： 1.两基因相同时产生+5，其余都是负数。 2.任意两个不同基因相配，直接配要好于分别与空碱基配。但是两基因不满足上1点的长度不同，所以必须有一些基因与空碱基相配。设f(...

2018-12-19

0 471

洛谷P1280 尼克的任务

https://www.luogu.org/problemnew/show/P1280 设d(i)为尼克从第i分钟开始着手工作一直到结束所花费的最少工作时间。 d(i)= d(i+1),i时无任务 d(i+t)+t,i时有一个任务 min{d...

2018-12-18

0 440

待解决问题

2018-12-18

0 329