더블 타워 DP

특정 제목 링크:클릭하여 링크 열기
A.【POJ 2609】Ferry Loading
B.【ZOJ 3331】Process the Tasks
두 대의 기계가 있는데 n(0개의 임무, 각 임무는 1번 기계를 사용하려면 T1이 걸리고, 2번 기계를 사용하려면 T2(0, i번째 임무가 완성될 때만 i+1개의 임무를 수행할 수 있다. 어떻게 해야 최종 소요 시간을 가장 짧게 할 수 있느냐고 물었다.
문제풀이 사고방식: 2차원수 그룹 dp[i][j]를 열면 첫 번째 임무를 처리한 후 시간차가 j시 탑의 높이임을 나타낸다.
1. A탑이 B탑보다 높다(j>=0):
a) A타워 위에 i번째 임무를 놓으면 시간차는 ta[i](i-1번째 임무를 완성해야만 i번째 임무를 수행할 수 있기 때문에 i-1번째 임무를 수행할 때 B타워는 i-1번째 임무를 완성할 때까지 정지 상태에 있다. 상태 이동 방정식: dp[i][ta[i]+time] =min(dp[i][ta[i]+time], dp[i-1][j+time]+ta[i])이다.
b) 첫 번째 임무를 탑 B에 놓으면 마지막 시간차는 j-tb[i]가 되고 상태 이동 방정식은 dp[i][j-tb[i]+time]=min(dp[i][j-tb[i]+time], dp[i-1][j+time]+max(tb[i]-j, 0)이다.
2、A탑은 B탑보다 낮다(j<0):(동상)
a) 첫 번째 퀘스트는 A 위에 놓습니다. dp[i] [j+ta[i]+time] =min(dp[i] [j+ta[i]+time], dp[i-1] [j+time] +max(0, j+ta[i])).
b) 첫 번째 작업은 B에 놓습니다. dp[i][-tb[i]+time] =min(dp[i][-tb[i]+time], dp[i-1][j+time]+tb[i]).

#include 
#include 
#include 
#include 
#include 
using namespace std;
const int inf=1e9;
const int N=110;
int dp[N][2*N];
int ta[N], tb[N];
int main()
{
	int t;
	scanf("%d", &t);
	while(t--)
	{
		int n;
		int time=100;
		scanf("%d", &n);
		for(int i=1; i<=n; i++) scanf("%d%d", &ta[i], &tb[i]);
		for(int i=0; i<=n; i++)
		{
			for(int j=0; j<210; j++)
				dp[i][j] = inf;
		}
		dp[0][time]=0;
		for(int i=1; i<=n; i++)
		{
			for(int j=-100; j<0; j++)
			{
				if(dp[i-1][j+time]==inf) continue;
				dp[i][-tb[i]+time] = min(dp[i][-tb[i]+time], dp[i-1][j+time]+tb[i]);
				dp[i][j+ta[i]+time] = min(dp[i][j+ta[i]+time], dp[i-1][j+time]+max(0, j+ta[i]));
			}
			for(int j=0; j<=100; j++)
			{
				if(dp[i-1][j+time]==inf) continue;
				dp[i][ta[i]+time] = min(dp[i][ta[i]+time], dp[i-1][j+time]+ta[i]);
				dp[i][j-tb[i]+time] = min(dp[i][j-tb[i]+time], dp[i-1][j+time]+max(tb[i]-j, 0));
			}
		}
		int ans=inf;
		for(int i=-100; i<=100; i++)
		{
			ans = min(ans, dp[n][i+time]);
		}
		printf("%d
", ans);
	}
	return 0;
}

C.【POJ 1015】 Jury Compromise
D.【ZOJ 2059】The Twin Towers
E.【UVA 10066】The Twin Towers