noip 范围的dp 优化

加速状态转移
1. 前缀和优化(计数)
2. 单调队列优化
3. 树状数组或线段树优化（线段树区间和阔以）
原理：找到数字之间的规律，加速状态
精简状态

对于基本状态，应使得式子精简，

前缀和优化

长度 \(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)\) 转移均摊到每个转移复杂度变小

一般形式

\[dp[i] = max\{f[j]\}+g[i]\\ dp[i] = max\{dp[j]+f[j]\}+g[i]\\ dp[l][i] = max\{dp[l-1][j]+f[j]\}+g[i] \]

注\ \(j\) 取值是一段连续区间，区间的两个端点随 \(i\) 的增大而增大的区间

如果左端固定，那么可以直接记录前缀最小值(固定扩大窗口，记录前缀和即可)

bzoj 1855 股票买卖

暴力DP状态

\(f[i][j]=\begin{cases}f[i-1][j]&no\ do\\f[i-1-w][k]-ap[i]\times(j-k)&buy\\ f[i-1-w][k]+bp[i]\times(k-j)&sell\end{cases}\)

解释一下为什么上边的\(j\), \(k\) 的关系，

当买入时，股票数在增加，故 \(j > k\)

当卖出时，股票数在减少，故 \(k > j\)

单调队列优化

取出其中一个化简得

\(f[i][j] = f[i-w-1][k]+ap[i]\times k- ap[i] \times 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)\)

\[f[i]=max\{f[j]|a[i] < a[j],i>j\}+1 \]

总结

特征总结，课后记

精简状态

挖掘题目性质特点

LIS 加长版

因为比较大小，无序了解数字的具体，利用离散化

换一思路

找一个最大值 \(k\) 满足条件存在 \(dp[j]=k\&\& a[j] < a[i]\)

没记。。。

如果前者大于后者，那么后者长度为k+1,那么可以提取k的子序列，他的元素要比上一个要，那么上一就不是最小值了，不符合定义条件（近似贪心）

二分+贪心

Noip 2008 传纸条

\(f[i][j][k][l]\)

枚举步数，ij分别表示两个纸条的横坐标，利用步数求得纵坐标

固定同行，除去冗杂真实坐标

~~wssb~~---Knight

DP现阶段优化