HOJ_14001 Just Terraffic!

题意相对来说比较扭曲。。所以来说下模型，具体做法有兴趣的孩纸去问度娘或者波塞冬吧~~

给出一个序列长度，并且输入该序列，该序列的含义是横坐标：

　　任何两个相邻坐标绝对值小于等于1000的必然为一个整体，

　　任何两个相邻坐标绝对值大于等于2000的必然是不同的两个整体，

　　其余有可能是，也有可能不是一个整体。

问，横跨三个坐标的整体有多少个，横跨两个坐标的整体有多少个？

如果唯一确定，则直接输出数量，否则输出“Ambiguous”

如果无解输出“Impossible”

直觉上认为这是有向无环图的DP问题，分别扫最大2坐标整体出现次数和最小2坐标整体出现次数。

如果二者中没有可行解，输出“Impossible”

如果二值不相等输出“Ambiguous”

否则直接按照要求输出即可。

时间复杂度是O（N）——状态总数n*每个状态决策数2*转移时间1

AC代码：

#include<iostream>

#include<stdio.h>

#include<string>

#include<string.h>

#include<vector>

#include<algorithm>

using namespace std;

const long long INF=1e8+233;

const long long MAXN=3000233;

long long n;

long long arr[MAXN];

long long dp1[MAXN];

long long dp2[MAXN];

void init()

{

//	memset(dp2,0,sizeof(dp2));

//	memset(arr,0,sizeof(arr));

//	memset(dp1,0,sizeof(dp1));

	for(long long i=0;i<n;++i)

	{

		dp1[i+1]=INF;

//		dp2[i+1]=0;

		cin>>arr[i];

	}

}

 

int main()

{

	cin.sync_with_stdio(false);

	while(cin>>n&&n)

	{

		init();

		dp1[0]=1;

		dp2[0]=1;

		for(long long i=0;i<n-1;++i)

		{

			if(dp1[i]!=INF&&dp2[i])

			{

				long long d1=10000;

				if(i+2<n)

				d1=arr[i+2]-arr[i+1];

				long long d2=arr[i+1]-arr[i];

				if(d1>1000&&d2<2000) dp1[i+2]=min(dp1[i+2],dp1[i]+1),dp2[i+2]=max(dp2[i+2],dp2[i]+1);

				long long d3=15000;

				if(i+3<n)d3=arr[i+3]-arr[i+2];

				if(i+3>n)continue;

			//	else continue;

				if(d1<2000&&d2<2000&&d3>1000)dp1[i+3]=min(dp1[i+3],dp1[i]),dp2[i+3]=max(dp2[i+3],dp2[i]);

			}

		}

		if(dp2[n]==dp1[n])

		{

			long long car2=dp2[n];

			car2--;

			n-=car2*2;

			long long car3=n/3;

			cout<<"Cars without trailers: "<<car2<<"\n";

			cout<<"Cars with trailers: "<<car3<<"\n";

		}else

		{

		if(dp1[n]==INF&&dp2[n]==0){cout<<"Impossible\n";break;}

			cout<<"Ambiguous\n";

		}

	}

	return 0;

}

巴特西

HOJ_14001 Just Terraffic!

最新文章

热门文章