URAL 1119 Metro

URAL 1119 Metro

/*
dp滚动数组
第一次用滚动数组
感觉挺好
之前用二维double型数组
MLE
在运行结果里看到有人用4080K过了(限制4M)
神人也。。。
*/
#define LOCAL
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<string>
#include<algorithm>
#include<ctime>
#include<stack>
#include<queue>
#include<vector>
#define N 1005
double dp1[N],dp2[N];
bool cross[N][N];
double minthree(double a,double b,double c)
{if(a<=b&&a<=c)return a;
else if(b<=a&&b<=c)return b;
else if(c<=a&&c<=b)return c;}
double mintwo(double a,double b)
{if(a<b)return a;else return b;}
using namespace std;
int main()
{
#ifdef LOCAL
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
#endif
 
	int n,m,ncross,i,j,x,y;
	double diag=100*sqrt((double)2);
	cin>>m>>n>>ncross;m++;n++;
	memset(dp2,0,sizeof(dp2));
	memset(cross,0,sizeof(cross));
	for(i=0;i<ncross;i++)
	{cin>>x>>y;cross[x][y]=true;}
	dp1[1]=0;
	for(i=2;i<=n;i++) {dp1[i]=dp1[i-1]+100;}
	for(i=2;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(j==1) {dp2[j]=dp1[j]+100;}
			else if(cross[i-1][j-1]) {dp2[j]=minthree(dp1[j-1]+diag,dp1[j]+100,dp2[j-1]+100);}
			else {dp2[j]=mintwo(dp1[j]+100,dp2[j-1]+100);}
		}
		memcpy(dp1,dp2,sizeof(double)*N);
		memset(dp2,0,sizeof(dp2));
	}
	cout<<(int)(dp1[n]+0.5)<<endl;
	return 0;
}

发表回复