HDU 5945 单调队列优化DP

比赛时一直以为是个数学题，一直没有想到用优先队列优化DP
看来需要好好学一学

STL中貌似没有直接对应的，所以用数组模拟队列就🆗，用空间换时间，比STL要快一些哦

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string> 
using namespace std;

int T,x,k,t,l,r;
int dp[1000100],q[1000100];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&x,&k,&t);
		memset(dp,0x3f,sizeof(dp));
		memset(q,0,sizeof(q));
		if(k == 0)
		{
			int s = 0;
			s = (x - 1) / t;
			printf("%d\n",s);
			continue;
		}
		if(t == 0)
		{
			int s = 0;
			while(x != 1)
			{
				s++;
				x /= k;
			}
			printf("%d\n",s);
			continue;
		}
		dp[1] = 0;
		q[1] = 1;
		l = 1; r = 1;
		for(int i = 2;i <= x; ++i)
		{
			while(l <= r && q[l] < i - t) l++;
			dp[i] = dp[q[l]] + 1;
			if(i % k == 0)
				dp[i] = min(dp[i] , dp[i / k] + 1);
			while(l <= r && dp[q[r]] >= dp[i]) r--;
			q[++r] = i;
		}
		printf("%d\n",dp[x]);
	}
    return 0;
}

形如dp[i]=max/min(f[k])+g[i] (k<i 且g[i]与k无关)时，可用单调队列优化。
优化的对象是f[k];

本来 i和k是要用两个for循环来套完，但是在此处，g[i]与k，无关，而f[k]又要滚动取最值，那么就可以在一个for循环中把f[k]得到最值，同时计算当前的g[i],(强调，for循环的遍历顺序要确定，要保证可能与g[i]产生结果的所有f[k]都已计算完毕)将两者的结果存入dp[i]中，就达到了降维的目的。

单调队列优化的DP，当然一定要有某一部分满足单调性，典型问题就是类似于滑动窗口问题，维护一个区间最值，随着所需要更新的元素变化而变化，然后看一个单调性特别的题。