noip 范围的dp 优化
-
加速状态转移
- 前缀和优化(计数)
- 单调队列优化
- 树状数组或线段树优化（线段树区间和阔以）
原理：找到数字之间的规律，加速状态
-
精简状态
对于基本状态，应使得式子精简，
前缀和优化
长度 (n) 逆序对为 (k) 的排列有几锅？
(K <=200)
(k <= 2000)
排列计数问题经典套路
满足排列套路，把1-n往后查，
(dp[i][j]) 前 (i) 个数 产生 (j) 的逆序对的方案数,
因为新插入的数是更大的所以,分别考虑插在最后边，次后边...
(dp[i+1][j+x]+=dp[i][j](x belong 0,1,2,...i+1))
往后转移
上面的式子向前转移为
(dp[i][j] = sum_{k=0}^{i-1}dp[i-1][j-k])
我们通过式子可以发现有取和的操作，如果每次操作都开一层循环来计算的话，时间复杂度会多以个 (n), 但是我们用前缀和优化则可以 (O(1)) 实现
做法如下：
方程：上述
我们设：
(f[i][j] = sum_{k=0}^{j}dp[i][k])
表示前 (i) 个数 产生 (j) 的逆序对的方案数的总和((i) 固定)
则转移为：
(dp[i][j] = f[i-1][j]-f[i-1][j-i])
这样直接转移则可以 (O(1)) 了
loj6077
在这个 (dp) 基础上，做容斥原理，通过之前讲的整数划分的模型 (dp) 求出容斥系数即可
总结
发现求和操作可以利用前缀和相减， 达到 (O(1))
转移区间是求和问题
单调队列优化（区间最大值）
从 (O(n)) 转移 均摊到每个转移复杂度变小
一般形式
注 (j) 取值是一段连续区间，区间的两个端点随 (i) 的增大而增大的区间
如果左端固定，那么可以直接记录前缀最小值(固定扩大窗口，记录前缀和即可)
bzoj 1855 股票买卖
暴力DP状态
(f[i][j]=egin{cases}f[i-1][j]&no do\f[i-1-w][k]-ap[i] imes(j-k)&buy\ f[i-1-w][k]+bp[i] imes(k-j)&sellend{cases})
解释一下为什么上边的(j), (k) 的关系，
当买入时， 股票数在增加，故 (j > k)
当卖出时， 股票数在减少，故 (k > j)
单调队列优化
取出其中一个化简得
(f[i][j] = f[i-w-1][k]+ap[i] imes k- ap[i] imes j)
发现存在 (k) 的式子是与先前的状态有关的，只有后一式子对(i,j) 的才产生影响，这种模型符合单调队列，
并且我们需要的决策点 (k) 与 (j) 存在一定的区间关系，即当 (j) 改变时，(k) 也在移动，进而形成了一个固定区间的移动窗口，以为窗口右移，存在单调性，故可以用单调队列
亮眼的地方：找到与坐标无关的（坐标值表包括决策内容，即(j)）和 与坐标有关的
利用的原因，我们想减少时间复杂度，因此可以将 (k) 那一维省去，利用单调队列，让队列中时刻保持当前最有用的多个决策点（这也是单调队列的普遍原理）
这样我们可以在转移时总时间复杂度达到 (O(N)) 转移，均摊下来就是 (O(N))
for (int j = 0; j <= maxp; j++)
{
f[i][j] = f[i-1][j]//no do
if (i <= w)//当不够w时，区间 w 只能进行一次操作，并且只能买股票
{
if(j <= as[i]) f[i][j] = max(f[i][j], j*ap[i])//控制买的数量,as表示一天买入最大值
}
while(head <= tail && id[head] < j - as[i]) head++;
}
hdu4374
区别
最大值和方案数
转移都是以区间，决策点方案求和的话就可以前缀和相减
前缀和--决策区间不一定单调递增
单调队列--决策区间必须是单调区间，
LIS加强版
区间最大值，带修改
线段树和树状数组
特征 每次坐标小于某个值的权值中的最大值
权值作为下标记录区间，权值线段树？？？？
时间复杂度 (O(NlogN))
总结
特征总结，课后记
精简状态
挖掘题目性质特点
LIS 加长版
因为比较大小，无序了解数字的具体，利用离散化
换一思路
找一个最大值 (k) 满足条件 存在 (dp[j]=k&& a[j] < a[i])
没记。。。
如果前者大于后者，那么后者长度为k+1,那么可以提取k的子序列，他的元素要比上一个要，那么上一就不是最小值了，不符合定义条件（近似贪心）
二分+贪心
Noip 2008 传纸条
(f[i][j][k][l])
枚举步数，ij分别表示两个纸条的横坐标，利用步数求得纵坐标
固定同行，除去冗杂真实坐标
wssb---Knight
**