[luoguP3572] [POI2014]PTA-Little Bird（DP + 单调队列）
传送门
DP方程
f[i] = f[j] + (a[j] <= a[i]) ( i k < j < i )
要使 f[i] 最小，需要等号后面的值最小，可以用单调队列来维护。
至于如何维护，具体看代码。
——代码
1 #include <cstdio> 2 3 const int MAXN = 1000005; 4 int n, k, Q, h, t; 5 int a[MAXN], q[MAXN], f[MAXN]; 6 7 inline bool cmp(int x, int y) 8 11 12 int main() 13 29 printf("%d\n", f[n]); 30 } 31 return 0; 32 }View Code
总结
这个题告诉我们，单调队列的单调性不仅仅只是个 < 或 > ，单调性是要满足最优解在一定在最前面。
下一篇：[luoguP1439] 排列LCS问题（DP + 树状数组）
DP 单调队列
pla文件怎么看，pla文件用什么打开？
pl1文件怎么看，pl1文件用什么打开？
pl文件怎么看，pl文件用什么打开？
pl0文件怎么看，pl0文件用什么打开？
pkt文件怎么看，pkt文件用什么打开？
pkm文件怎么看，pkm文件用什么打开？
pks文件怎么看，pks文件用什么打开？
pka文件怎么看，pka文件用什么打开？
pkh文件怎么看，pkh文件用什么打开？
pkg文件怎么看，pkg文件用什么打开？