CF1209E Rotate Columns
DP 题解 OI http://codeforces.com/problemset/problem/1209/E2http://codeforces.com/problemset/problem/1209/E2 这是一道最近 Codeforces 比赛的题目, 当时在场上昏昏欲睡, 连小的点都没有想出来, 现在再看一下. 题意 给你一个的矩阵, 可以对每一列的元素循环移位, 求每一行的最...
CF273D Dima and Figure
DP 题解 OI http://codeforces.com/problemset/problem/273/Dhttp://codeforces.com/problemset/problem/273/D 题意 在的方格纸上选择一个四连块, 要求对于四连块中的任意两点之间的最小移动距离等于他们之间的曼哈顿距离. 问有多少种选法. 分析 条件的意思是选出的格子集是凸的, 即: 左边界先减后增, ...
洛谷P2607 [ZJOI2008]骑士
DP 题解 OI https://www.luogu.org/problemnew/show/P2607https://www.luogu.org/problemnew/show/P2607 经典题，n个点n条边的图一定是一个基环树森林，于是可以先DFS一遍把环找出来，再断环（在环上随便找一条边，强制两个端点之一不选），就变成了一个没有上司的舞会了。 123456789101112131...
洛谷P3195 [HNOI2008]玩具装箱TOY
DP 题解 OI https://www.luogu.org/problemnew/show/P3195https://www.luogu.org/problemnew/show/P3195 经典的一道斜率优化DP,很久以前写的,现在再拿出来复习一下 简单读题可以得出本题的DP方程是 但是这样转移的复杂度高达,5e4的数据不能接受,需要优化. 为了简便计算,令. 假设存在决策和(),...