[luoguP3146] [USACO16OPEN]248（区间DP）

传送门

f[i][j]表示区间 ij 合并的最大值

转移：

若f[i][k] && f[k+1][j] && f[i][k] == f[k+1][j] > f[i][j] = max(f[i][k]+1,f[i][j])

但要注意， 若f[i][k]!=f[k+1][j]，那么无法进行转移

代码

#include <cstdio> #include <iostream> #define max(x, y) ((x) > (y) ? (x) : (y)) int n, ans; int f[5001][5001]; inline int read() int main() printf("%d\n", ans); return 0; }

　　

上一篇：[luoguP1373] 小a和uim之大逃离（DP）

下一篇：[luoguP1056] 排座椅（sort + 模拟）

---

DP