Absoler

思维

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

全部文章 / 思维（共2篇）

区间DP

HDU4283 题目中的小黑屋就是一个栈，因此在处理区间时要考虑栈的特点，即“区间嵌套性”。我们令dp[i][j]代表区间[i , j]的最小代价，注意这里是单看这一个区间，即a[i]为首元素。接下来讨论a[i]的出现次序，设第k个出现，则[i+1, i+k-1]元素必将在第1~k-1个次序出现，...

2020-05-09

0 476

codeforces/1312E（区间dp）

题目这道题不管从内容还是数据范围看起来都像是区间dp，可一时想不出来怎么构造出一个满足无后效性的区间状态，看了一眼题解才顿悟。分两步走，第一步我们求出所有的dp[l][r]，表示[l,r]区间可以最终转化为的一个数，如果无法转化则为零，这一步的巧妙就在于包含了足够的信息来“总结”这个区间。第...

2020-05-09

0 760