王翔宇2
王翔宇2
全部文章
未归档
归档
标签
去牛客网
登录
/
注册
xxy
全部文章
/ 未归档
(共2篇)
P4766 [CERC2014]Outer space invaders
自行想象传送门 题解 当我们一看到这个题的tag时就知道这是一道区间dp水题 很明显这个区间就是指时间上的区间 我们用dp[i][j]表示时间i~j之间消灭所有的aliens的最小代价 很明显开不下这么大的二维数组赛 所以离散化一下不久过了?? 状态转移方程 dp[i][j]=min(...
2019-09-03
0
349
[IOI1998]Polygon
luogu传送门 题解 一道经典的区间DP,既又环形结构,又需要思考怎样维护“最优子结构”的性质 首先我们不难想到用dp[l,r]表示第l个节点和第r个节点合并后最大顶点上的最大值 如果只是有加法运算,其实就与合并石子无异 但问题来了——有乘法 所以如果我们只维护最大值,显然不对 ...
区间DP
2019-08-22
1
450