[NOIP2018][낙곡P5017] 나룻배[DP]

제목 대의:

제목 링크:https://www.luogu.org/problemnew/show/P5017nn이 있는데 각각 t1∼tnt1\sim t_nt1∼tn의 시간에 도착하면 한 대의 나룻배는 이들을 다른 곳으로 보내야 한다. 나룻배는 한 번 mm의 시간 단위를 왕복해야 한다.이 사람들 최대한 빨리 보내달라고.

아이디어:

틀림없이 먼저 ttt를 정렬할 수 있을 것이다.우리는 한 사람이 도착한 후에 발차하는 것은 단지 두 가지 상황일 뿐이라는 것을 안다.

나룻배는 그가 도착하기 전에 도착했다.이때 바로 발차할 수 있다.

나룻배는 그가 도착한 후 kk분에야 도착했다.이때 kkk분을 기다려야 출발할 수 있다.

먼저 s[i][j]s[i][j]s[j][j]를 미리 처리할 수 있으며, iii개인이 jjj개인과 같은 차를 타는 대기 시간을 나타낸다.그러면 s[i] [j] = ∑j = 1 n ∑i = 1 j - 1 ∑k = i j - 1 t j - t ks [i] [j] =\sum^ {n}{j=1}\sum^{j-1}_{i=1}\sum^{j-1}_{k=i}t_j-t_ks[i][j]=j=1∑ni=1∑j-1k=i∑j-1tj-1tj-3tk 그러면 f[i][j]f[i][j][j]는 ii i가 도착하면 출발하고 ii i는 j 분을 기다리는 최소 대기 시간을 나타낸다.그러면 반드시 jjj를 일일이 열거해야 한다. 이것은 전 jjj 개인이 이미 목적지에 도착했다는 것을 의미한다.그러면 iii 개인이 도착했을 때 나룻배가 돌아왔다면 바로 출발할 수 있다(즉 ii 개인의 대기시간은 0.00).이때 f[i][0] = min(f[i][0], f[j][k] + s[j+1] [i]) f[i][0]]=min(f[i]]]][0], f[j][k]+s[j+1][i]) f[i][0]]]=min(f[i][0], f[j][k]+s[j+1][i]) 중 kkkk는 제jj 개인이 기다리는 시간을 나타낸다.그러면 ii i 개인이 도착해서 페리카가 돌아오지 않으면 ii 개인이 기다리는 시간은 w = t j + k + m - 6 - t i w=tj+k+m-t_i w=tj+k+m - ti 중 tj+k+m tj+k+m tj+k+m는 나룻배가 돌아오는 시간이다.그러면 f [i] [w] = m in(f[i] [w], f [j] [k] + s [j + 1] [i] + (i) + (i j) w w f[i] [w] [w] [w] f[i] [w] [w] f[j] [k] + s [j+1] [i] + (i] + (i] + (i] + (i] + (i) + (i- j) + (i-j) * w) f [i] [w] [w] [w] [w] [w] f[i] [w] [w] f[[[j] [j] [j] + s] + s+ j + i] [j]++ i(j] i]++ ii) + ii(w) f[w] [w] [w] + if[n][i])(i=0∼m)min(f[n][i])(i=0\sim m)min(f[n][i])(i=0∼m)시간 복잡도 O(n2m)O(n^2m)O(n2m)로 본제를 넘기기에 충분하다.

코드:

#include 
#include 
#include 
using namespace std;

const int N=510;
const int M=210;
const int Inf=2e9;
int n,m,ans,w,t[N],f[N][M],s[N][N];

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&t[i]);
	sort(t+1,t+1+n);
	for (int j=1;j<=n;j++)
		for (int i=1;i<j;i++)
			for (int k=i;k<j;k++)
				s[i][j]+=t[j]-t[k];
	memset(f,0x3f3f3f3f,sizeof(f));
	t[0]=-Inf;
	for (int i=0;i<=m;i++)  //   
	{
		f[0][i]=0;
		f[1][i]=i;
	}
	for (int i=2;i<=n;i++)
		for (int j=0;j<i;j++)
			for (int k=0;k<=m;k++)
			{
				w=t[j]+k+m-t[i];
				if (w>0)
					f[i][w]=min(f[i][w],f[j][k]+s[j+1][i]+(i-j)*w);
				else
					f[i][0]=min(f[i][0],f[j][k]+s[j+1][i]);
			}
	ans=Inf;
	for (int i=0;i<=m;i++)
		ans=min(ans,f[n][i]);
	printf("%d
",ans);
	return 0;
}