POJ 2373

原本一道挺简单的DP题，思路有了，运用单调队列，但在写单调队列时写挫了。。。

这道题只需要计算偶数位置的即可，这是显而易见的，我有注意过这情况，写的时候却没在意。。。--!

加入队列的元素应该当前now之前的now-2*A的元素，我开始不是每计算一个now位置就加入now-2*A的元素，搞得不是O(L)的复杂度。这次吸取教训了。。记得DP时使用单调队列一般每计算一个位置加入一个元素。

PS：

又回想起之前比赛，感觉很害怕。。希望自己加油吧。

我的代码：不知为何没能过。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <climits>

#include <string.h>

#include <queue>

#include <cmath>

#include <vector>

using namespace std;

const int N=1000100;

const int inf=1<<30;

int dp[N],que[N],f,l,p;

struct Node{

	int l,r;

	Node(){l=0,r=0;}

	Node(int ll,int rr){l=ll,r=rr;}

	bool operator <(const Node &a)const{

		if(l<a.r) return true;

		return false;

	}

};

Node node[1010];

int n,L,a,b;

void Mergeinter(){

/*	int top=0;

	for(int i=1;i<n;i++){

		if(node[i].l<node[top].r&&node[top].r<node[i].r)

		node[top].r=node[i].r;

		else if(node[i].l<node[top].r&&node[top].r>=node[i].r) continue;

		else{

			top++;

			node[top].l=node[i].l;

			node[top].r=node[i].r;

		}

	}

	n=top;*/

    int top=0;

    int l=node[0].l,r=node[0].r;

    for(int i=1;i<n;i++){

        if(node[i].l<r){

            r=max(r,node[i].r);

        }else{

            node[top++]=Node(l,r);

            l=node[i].l;

            r=node[i].r;

        }

    }

    node[top++]=Node(l,r);

    n=top;

}

void Pop(int now){

	while(f<l){

		if(now-que[f]<=b) break;

		f++;

	}

}

void Push(int now){

	while(f<l){

		if(dp[que[l-1]]<dp[now-a]) break;

		l--;

	}

	que[l++]=now-a;

}

int main(){

	while(scanf("%d%d",&n,&L)!=EOF){

		scanf("%d%d",&a,&b);

		for(int i=0;i<n;i++){

			scanf("%d%d",&node[i].l,&node[i].r);

		}

		if(L%2==1){ printf("-1\n");continue; }

		f=l=p=0;

		sort(node,node+n);

		Mergeinter();

		a*=2;b*=2;

		dp[0]=0;

		for(int i=2;i<a;i+=2) dp[i]=inf;

		for(int i=a;i<=L;i+=2){

			Pop(i);

			Push(i);

			while(p<n&&node[p].r<=i) p++;

			if(p<n&&node[p].l<i||dp[que[f]]==inf) dp[i]=inf;

			else dp[i]=dp[que[f]]+1;

		}

		if(dp[L]==inf) printf("-1\n");

		else printf("%d\n",dp[L]);

	}

	return 0;

}

引用别人的：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <vector>

#include <algorithm>

using namespace std;

const int MAX=1001000;

const int oo=0x3f3f3f3f;

int dp[MAX];

struct Seg{

	int x,y;

	Seg(int x=0,int y=0):x(x),y(y){}

	bool operator<(const Seg& seg) const{

		return x<seg.x;

	}

}seg[1100];

int q[MAX],id[MAX],f,b;

int merge(int n){

	int top=0;

	sort(seg,seg+n);

	int l=seg[0].x,r=seg[0].y;

	for(int i=1;i<n;i++){

		if(seg[i].x<r){

			r=max(r,seg[i].y);

		}else{

			seg[top++]=Seg(l,r);

			l=seg[i].x;

			r=seg[i].y;

		}

	}

	seg[top++]=Seg(l,r);

	return top;

}

int main(){

	int n,L,l,r,p;

	scanf("%d%d",&n,&L);

	if(L&1){

		printf("%d\n",-1);

		return 0;

	}

	scanf("%d%d",&l,&r);

	for(int i=0;i<n;i++){

		scanf("%d%d",&seg[i].x,&seg[i].y);

	}

	n=merge(n);

	l<<=1;

	r<<=1;

	dp[0]=0;

	f=b=0;

	p=0;

	dp[0]=0;

	for(int i=2;i<l;i+=2)dp[i]=oo; //start with 2.

	for(int i=l;i<=L;i+=2){

		while(f!=b&&i-id[f]>r)f++;

		while(f!=b&&q[b-1]>=dp[i-l])b--;

		id[b]=i-l;

		q[b++]=dp[i-l];

		while(p<n&&seg[p].y<=i)p++;

		if(p<n&&seg[p].x<i||q[f]==oo)dp[i]=oo;	 //if q[f] is oo, not to set dp[i] = q[f]+1.

		else dp[i]=q[f]+1;

	}

	//for(int i=0;i<=L;i+=2)printf("%d ",dp[i]==oo?-1:dp[i]);puts("");

	printf("%d\n",dp[L]==oo?-1:dp[L]);

	return 0;

}

巴特西

POJ 2373

最新文章

热门文章