HDU 4258 Covered Walkway [단일 큐 기울기 최적화]

1283 단어
아이디어:
제목에서 주의해야 할 몇 가지 점:
(1) The points will be in order, from smallest to largest(점별 정렬)
         (2)Note that it is possible for x=y. If so, then the contractor would simply charge c. 
상태 전환 방정식:
         dp[i]=min{dp[j]+(x[i]-x[j+1])^2+c}(0(dp[i]는 앞의 i점의 비용을 나타낸다)
AC 코드:
#include<stdio.h>
#define N 1000005
_int64  x[N];
_int64 dp[N];
int q[N];
int head,tail;
_int64 c;
int n;
_int64 getDp(int i,int j)
{
     return dp[j]+c+(x[i]-x[j+1])*(x[i]-x[j+1]);
}
_int64 getUp(int j,int k)
{
     return dp[j]+x[j+1]*x[j+1]-(dp[k]+x[k+1]*x[k+1]);
}
_int64 getDown(int j,int k)
{
     return 2*(x[j+1]-x[k+1]);
}
int main()
{
	int i;
	while(scanf("%d%I64d",&n,&c)!=-1&&(n+c))
	{
	    for(i=1;i<=n;i++)
			scanf("%d",&x[i]);
		dp[0]=0;
		head=tail=0;
		q[tail++]=0;
		for(i=1;i<=n;i++)
		{
		 while(head+1<tail&&getUp(q[head+1],q[head])<=x[i]*getDown(q[head+1],q[head]))
			 head++;
		 dp[i]=getDp(i,q[head]);
		 while(head+1<tail&&getUp(q[tail-1],q[tail-2])*getDown(i,q[tail-1])>=getUp(i,q[tail-1])*getDown(q[tail-1],q[tail-2]))
			 tail--;
		 q[tail++]=i;
		}
		printf("%I64d
",dp[n]); } return 0; }

좋은 웹페이지 즐겨찾기