JOI20 Collecting Stamps 3

문제

https://oj.uz/problem/view/JOI20_ho_t3

문제 보기 - Collecting Stamps 3 (JOI20_ho_t3) :: oj.uz

원 위에 수행해야 하는 작업들의 위치 X, 수행해야 하는 시간 T가 주어질 때 원점에서 출발하여 각 시계방향, 반시계방향으로 움직이며 작업들을 수행해야 한다. 좌표 1칸을 이동할 때 1의 시간이 소요되고, 작업을 T이내에 수행한다면 보상을 받을 수 있을 때 전체 보상의 최대값을 구해야 한다.

$N<=200$

$L, X_i, T_i<=10^9$

 

풀이

Observation 1 : 최적해는 원점에서 출발하여 시계 방향으로 일정 거리만큼 이동하고, 반시계 방향으로 이동하고, 다시 시계 방향으로 이동하며 각 단계별로 한번도 방문하지 않은 정점들을 새롭게 방문하는 꼴이다.

당연히 각 작업은 처음 방문할 때 수행하는 것이 이득이고, 시계 방향으로 이동하다가 방향을 바꾸어 반시계 방향으로 이동하기 시작했다는 것은 지금까지 방문하지 않은 새로운 점을 방문하기 위함이다.

 

위 관찰을 통해 다음과 같은 DP 풀이를 생각해 볼 수 있다.

$dp(l, r, t) =$시계 방향으로는 $l$만큼 방문했고, 반시계 방향으로는 $r$까지 방문했으며, 시간이 $t$흘렀을 때 보상의 최댓값

현재 위치가 시계 방향쪽인지, 반시계 방향쪽인지에 따라 dp1, dp2를 관리하면 $O(N^2T)$의 시간 안에 해결할 수 있다. 

 

하지만 T의 범위가 매우 크니, 다음과 같이 dp의 답과 인자를 바꿈으로서 해결할 수 있다.

$dp(l, r, k) =$시계 방향으로는 $l$만큼 방문했고, 반시계 방향으로는 $r$까지 방문했으며, $k$의 보상을 얻기 위한 최소 시간

 

전체 상태의 개수가 $O(N^3)$개이고, 전이의 개수도 똑같으니, $O(N^3)$으로 문제를 해결할 수 있다.

 

시간 복잡도 : $O(N^3)$

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 200;
const ll INF = 1e18;
 
int N, L, X[MAXN+10], T[MAXN+10], ans;
ll dp1[MAXN+10][MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10][MAXN+10];
 
int main()
{
	scanf("%d%d", &N, &L);
	for(int i=1; i<=N; i++) scanf("%d", &X[i]);
	for(int i=1; i<=N; i++) scanf("%d", &T[i]);
	X[N+1]=L;
 
	for(int i=0; i<=N; i++)
	{
		for(int j=N+1; j>=i+1; j--)
		{
			for(int k=0; k<=N; k++)
			{
				if(i==0 && j==N+1)
				{
					if(k==0) dp1[i][j][k]=dp2[i][j][k]=0;
					else dp1[i][j][k]=dp2[i][j][k]=INF;
					continue;
				}
				ll t=INF;
				if(i>=1)
				{
					if(k && dp1[i-1][j][k-1]+X[i]-X[i-1]<=T[i]) t=min(t, dp1[i-1][j][k-1]+X[i]-X[i-1]);
					if(dp1[i-1][j][k]+X[i]-X[i-1]>T[i]) t=min(t, dp1[i-1][j][k]+X[i]-X[i-1]);
 
					if(k && dp2[i-1][j][k-1]+L-X[j]+X[i]<=T[i]) t=min(t, dp2[i-1][j][k-1]+L-X[j]+X[i]);
					if(dp2[i-1][j][k]+L-X[j]+X[i]>T[i]) t=min(t, dp2[i-1][j][k]+L-X[j]+X[i]);
				}
				dp1[i][j][k]=t;
 
				t=INF;
				if(j<=N)
				{
					if(k && dp2[i][j+1][k-1]+X[j+1]-X[j]<=T[j]) t=min(t, dp2[i][j+1][k-1]+X[j+1]-X[j]);
					if(dp2[i][j+1][k]+X[j+1]-X[j]>T[j]) t=min(t, dp2[i][j+1][k]+X[j+1]-X[j]);
 
					if(k && dp1[i][j+1][k-1]+X[i]+L-X[j]<=T[j]) t=min(t, dp1[i][j+1][k-1]+X[i]+L-X[j]);
					if(dp1[i][j+1][k]+X[i]+L-X[j]>T[j]) t=min(t, dp1[i][j+1][k]+X[i]+L-X[j]);
				}
				dp2[i][j][k]=t;
 
				if(dp1[i][j][k]!=INF) ans=max(ans, k);
				if(dp2[i][j][k]!=INF) ans=max(ans, k);
 
				//if(j==11) printf("%d %d %d : %lld %lld\n", i, j, k, dp1[i][j][k], dp2[i][j][k]);
			}
		}
	}
	printf("%d\n", ans);
}