hdu-3507-Print Article

1602 단어
/*처음으로 경사율 dp를 만들었는데 그것이 정말 강하고 선형 단조로운 대기열로 dp를 최적화하는 사고방식과 차이가 많지 않다는 것을 발견했다.여기도 단조로운 사율 대열을 유지하여 각 지점이 최대 한 번만 대열에 들어갈 수 있도록 보증한다.시간이 복잡하다×n) o(n)로 내려갔다.주로 G(i, j)*/
  
#include<stdio.h>
#include<string.h>
__int64 dp[510000],sum[510000];
__int64 G(int i,int j){return dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j];}
__int64 g(int i,int j){return 2*sum[i]-2*sum[j];}
int q[510000];
int main()
{
 int n,m,i,head,tail;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
  for(i=1,sum[0]=0;i<=n;i++)
  {
   scanf("%I64d",&sum[i]);
   sum[i]+=sum[i-1];
  }
  head=0;
  tail=1;
  memset(q,0,sizeof(q));
  memset(dp,0,sizeof(dp));
  for(i=1;i<=n;i++)
  {
   while(head+1<tail&&G(q[head+1],q[head])<=sum[i]*g(q[head+1],q[head]))head++;
   dp[i]=dp[q[head]]+m+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]]);
   while(head+1<tail&&G(i,q[tail-1])*g(q[tail-1],q[tail-2])<=G(q[tail-1],q[tail-2])*g(i,q[tail-1]))tail--;
   q[tail++]=i;
  }
  printf("%I64d
",dp[n]);
 }
 return 0;
}
Rails Tutorial 제4장 조견표
[코딩테스트 예제] 등굣길

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage