AFreeMan

区间型DP

BFS(1) CDQ分治和整体二分(1) Codeforces(15) DFS(4) GDUT训练(8) KMP(1) MST(1) RMQ(2) Trie(1) 二分(3) 几何(2) 单调栈(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)

/ 注册

全部文章 / 区间型DP （共5篇）

2019华工校赛 A.NB群友

https://ac.nowcoder.com/acm/contest/625/A 题意：求每位数字为 2 − 9 ...

2019-04-14

0 431

Codeforces1114 D. Flood Fill

http://codeforces.com/contest/1114/problem/D You are given a line of nn colored squares in a row, numbered from 11 to nn from left to right. The ii -...

2019-02-11

0 543

洛谷P1040 加分二叉树

https://www.luogu.org/problemnew/show/P1040 这道题看上去是二叉树，实际上就是一个简单的区间DP，因为其中序遍历是1~n，可按区间dp的方法做。设f(i,j):编号i~j的子树的最大分数。则以树根划分，f(i,j)=max{f(i,k-1)*f(k...

2019-01-02

0 419

洛谷P1026 统计单词个数

https://www.luogu.org/problemnew/show/P1026 对这句话“当选用一个单词之后，其第一个字母不能再用”需要特殊处理一下，贪心，如果包含this，th，t则等价于只包含t，即几个单词开头相等并且有完全包含关系，则保留最短的那个即可，针对上述3个单词给个例子：th...

2018-12-23

0 563

洛谷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