HDU 5945 단일 대기열 최적화 DP

1540 단어
시합할 때 줄곧 수학 문제인 줄 알았는데, 우선순위로 DP를 최적화할 줄은 생각지도 못했다. 보아하니 잘 배워야 할 것 같다
STL에 직접 대응하는 것이 없는 것 같아서 수조로 대기열을 시뮬레이션하면?,공간으로 시간을 바꿔서 STL보다 빠르네요.
#include
#include
#include
#include
#include 
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
",s); continue; } if(t == 0) { int s = 0; while(x != 1) { s++; x /= k; } printf("%d
",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
",dp[x]); } return 0; }

예를 들어 dp[i]=max/min(f[k])+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는 반드시 어떤 부분이 단조성을 만족시켜야 한다. 전형적인 문제는 슬라이딩 창 문제와 유사하고 한 구간의 최고치를 유지하며 업데이트가 필요한 요소의 변화에 따라 변화하는 것이다. 그리고 단조로운 특별한 문제를 본다.

좋은 웹페이지 즐겨찾기