【BZOJ3379】【USACO2004】交作业区间DP

题目描述

　　数轴上有$n$个点，你要从位置$0$去位置$B$，你每秒钟可以移动$1$单位。还有$m$个限制，每个限制$(x,y)$表示你要在第$t$秒之后（可以是第$t$秒）经过位置$y$。问你最少需要几秒。

　　$n\leq 1000$。

题解

　　可以发现如果$B\leq x_i\leq x_j$且$y_i\leq y_j$那么第$i$个限制就没有效果。所以我们每次一定是选择当前还没走过的最边上两个端点之一，走过去，然后等待。

　　这样就可以DP了。

　　设$f_{i,j,0}$为$i$_{$j$这些限制还没有满足且当前在$x_i$的最小时刻，$f_{i,j,1}$为$i$}$j$这些限制还没有满足且当前在$x_j$的最小时刻。这样就可以区间DP了。

　　时间复杂度：$O(n^2)$

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<cmath>

#include<functional>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

void sort(int &a,int &b)

{

	if(a>b)

		swap(a,b);

}

void open(const char *s)

{

#ifndef ONLINE_JUDGE

	char str[100];

	sprintf(str,"%s.in",s);

	freopen(str,"r",stdin);

	sprintf(str,"%s.out",s);

	freopen(str,"w",stdout);

#endif

}

struct xj

{

	int x,t;

};

xj a[1010];

int cmp(xj a,xj b)

{

	return a.x<b.x;

}

int f[1010][1010][2];

int main()

{

	int n,orzxj,k;

	scanf("%d%d%d",&n,&orzxj,&k);

	int i,j;

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

		scanf("%d%d",&a[i].x,&a[i].t);

	a[++n].x=k;

	a[n].t=0;

	sort(a+1,a+n+1,cmp);

	int x;

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

		if(a[i].x==k&&!a[i].t)

			x=i;

	for(i=1;i<=x;i++)

		for(j=n;j>=x;j--)

			if(i==1&&j==n)

			{

				f[i][j][0]=max(a[i].x,a[i].t);

				f[i][j][1]=max(a[j].x,a[j].t);

			}

			else

			{

				f[i][j][0]=f[i][j][1]=0x7fffffff;

				if(j!=n)

				{

					f[i][j][0]=min(f[i][j][0],max(a[i].t,f[i][j+1][1]+a[j+1].x-a[i].x));

					f[i][j][1]=min(f[i][j][1],max(a[j].t,f[i][j+1][1]+a[j+1].x-a[j].x));

				}

				if(i!=1)

				{

					f[i][j][0]=min(f[i][j][0],max(a[i].t,f[i-1][j][0]+a[i].x-a[i-1].x));

					f[i][j][1]=min(f[i][j][1],max(a[j].t,f[i-1][j][0]+a[j].x-a[i-1].x));

				}

			}

	printf("%d\n",f[x][x][0]);

	return 0;

}

巴特西

【BZOJ3379】【USACO2004】交作业区间DP

题目描述

题解

代码

最新文章

热门文章

巴特西

【BZOJ3379】【USACO2004】交作业 区间DP

题目描述

题解

代码

最新文章

热门文章

【BZOJ3379】【USACO2004】交作业区间DP