ZOJ 3632 Watermelon Full of Water(단일 업데이트, 구간 조회)

제목: n일이 있으면 매일 수박을 살 수 있습니다. 수박마다 가격은ai이고 수박마다bi일을 먹을 수 있습니다.-- 이 n일 매일 수박을 먹는 가장 적은 대가는 얼마인가.만약 네가 이튿날 수박을 하나 샀다면, 이전에 산 수박은 모두 버려야만 새로운 수박을 먹기 시작할 수 있다.
dp[i]를 i일까지 매일 수박을 먹는 최소한의 대가로 정의하면 상태 이동 방정식은 dp[i]=min(dp[i], dp[i-k-1]+a[i-k])이다.이렇게 하면 시간의 복잡도가 O(n^2)에 도달하기 때문에 최적화해야 한다.점차적으로 미루는 과정에서 우리는 i-k일에 도달한 후에 i-k+1일에서 i일까지의 대가를 갱신한다.만약 우리가 이 범위를 한꺼번에 갱신할 수 있다면 복잡도를 낮출 수 있을 것이다. 최적화된 방법은 바로 라인 트리이다.
전환하는 방법은 여전히 매우 교묘하다.i-k일에 대해 우리는 i일째의 이 점만 업데이트하고 조회할 때 우리는 i일째에서 n일째의 최소치를 조회한다. 만약에 우리가 얻은 것이 i일째에서 n일째의 어느 최소치라면 이 최소치는 반드시 i일째나 i-1일 전에 업데이트된 것이다.곰곰이 생각해 볼 수 있다.

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long LL;
#define INF ((LL)1<<60)
const int N=50005;
int day[N],valu[N];
LL dp[N];
struct node
{
	int left,right;
	LL imin;
	int mid(){return left+(right-left)/2;}
	void change(LL valu){imin=min(imin,valu);}
};
struct Segtree
{
	node tree[N*4];
	void build(int left,int right,int ind)
	{
		tree[ind].left=left;	tree[ind].right=right;
		tree[ind].imin=INF;
		if(left!=right)
		{
			int mid=tree[ind].mid();
			build(left,mid,ind*2);
			build(mid+1,right,ind*2+1);
		}
	}
	void updata(int pos,int ind,LL valu)
	{
		if(tree[ind].left==tree[ind].right) tree[ind].change(valu);
		else 
		{
			int mid=tree[ind].mid();
			if(pos<=mid) updata(pos,ind*2,valu);
			else updata(pos,ind*2+1,valu);
			tree[ind].imin=min(tree[ind*2].imin,tree[ind*2+1].imin);
		}
	}
	LL query(int be,int end,int ind)
	{
		int left=tree[ind].left,right=tree[ind].right;
		if(be<=left&&right<=end) return tree[ind].imin;
		else 
		{
			int mid=tree[ind].mid();
			LL imin1=INF,imin2=INF;
			if(be<=mid) imin1=query(be,end,ind*2);
			if(end>mid) imin2=query(be,end,ind*2+1);
			return min(imin1,imin2);
		}
	}
}seg;
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%d",&valu[i]);
		for(int i=1;i<=n;i++) scanf("%d",&day[i]);

		dp[0]=0;
		seg.build(1,n,1);
		for(int i=1;i<=n;i++)
		{
			int pos=i+day[i]-1;
			if(pos>n) pos=n;
			seg.updata(pos,1,dp[i-1]+valu[i]);
			dp[i]=seg.query(i,n,1);
		}
		printf("%lld
",dp[n]);
	}
	return 0;
}

단조로운 대기열로 최적화할 수도 있어요.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int N=50005;
int data[N],day[N];
LL dp[N];
struct node
{
	LL valu,ind;
	node(){}
	node(LL a,LL b){valu=a;ind=b;}
	bool operator<(const node &b)const
	{
		return valu>b.valu||(valu==b.valu&&ind>b.ind);
	}
};
int main()
{
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++) scanf("%d",&data[i]);
		for(int i=1;i<=n;i++) scanf("%d",&day[i]);

		dp[0]=0;
		priority_queue<node> que;
		for(int i=1;i<=n;i++)
		{
			node tmp=node(dp[i-1]+data[i],i+day[i]-1);
			while(!que.empty()&&que.top().ind<i) que.pop();
			que.push(tmp);
			dp[i]=que.top().valu;
		}
		printf("%lld
",dp[n]);
	}
	return 0;
}