记录编号	185764	评测结果	AAAAAAAAAA
题目名称	[CTSC 2000]公路巡逻	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	1.032 s
提交时间	2015-09-08 20:58:23	内存使用	102.51 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int SIZEN=310,INF=0x7fffffff/2;
int n,m;
int st[SIZEN],S[SIZEN],T[SIZEN];//出发点，出发时间，消耗时间
int early[SIZEN],last[SIZEN];//最早到达和最晚到达i点的时间
int f[SIZEN][60*60*24+10];
int getsecond(int t)//把时，分，秒转化为秒
{
	int re=0;
	re+=t%100;t/=100;
	if(t>0) {re+=(t%100)*60,t/=100;}
	if(t>0) {re+=(t%100)*3600,t/=100;}
	return re;
}
int w(int x,int stime,int entime)
{
	int re=0;
	for(int i=1;i<=m;i++)
	{
		if(st[i]!=x) continue;
		if(S[i]==stime)
		{
			if(S[i]+T[i]==entime) re++;
			continue;
		}
		if(S[i]<stime)
		{
			if(S[i]+T[i]>=entime) re++;
		}
		if(S[i]>stime)
		{
			if(S[i]+T[i]<=entime) re++;
		}
    }
	return re;
}
int get(int a)
{
	int re=0;
	re=a%60;a/=60;
	if(a>0) {re+=(a%60)*100,a/=60;}
	if(a>0) {re+=(a%60)*100*100,a/=60;}
	return re;
}
void DP()
{
	for(int i=1;i<=n;i++)
	{
		early[i]=getsecond(60000)+300*(i-1);
		last[i]=early[i]+300*(i-1);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=early[i]-300;j<=last[i]+300;j++) f[i][j]=INF;
	}
	f[1][getsecond(60000)]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=early[i];j<=last[i];j++)
			for(int k=300;k<=600;k++)
			{
				if(f[i-1][j-k]==INF) continue;
				f[i][j]=min(f[i-1][j-k]+w(i-1,j-k,j),f[i][j]);
				if(!f[i][j]) break;
			}
	}
	int ans=INF,ans1=0;
	for(int i=early[n];i<=last[n];i++)
	{
		if(f[n][i]<ans)
		{
			ans=f[n][i];
			ans1=i;
			//cout<<i<<" "<<ans1<<endl;
		}
	}
	//cout<<early[n]<<" "<<last[n]<<endl;
	printf("%d\n",ans);
	printf("%06d\n",get(ans1));
}
int main()
{
	freopen("patrol.in","r",stdin);
	freopen("patrol.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&st[i]);
		string a;
		cin>>a;
		int tem=0;
		for(int j=0;j<a.size();j++)
			tem=tem*10+a[j]-'0';
		S[i]=getsecond(tem);
		scanf("%d",&T[i]);
	}
	DP();
	return 0;
}