ZOJ 3331 Process the Tasks

本文由 Ocrosoft 于 2017-02-15 16:38:54 发表

Process the Tasks


Time Limit: 1 Second      Memory Limit: 32768 KB


There are two machines A and B. There are n tasks, namely task 1, task 2, …, task n. You must assign each task to one machine to process it. There are some facts you must know and comply with:

  • You must assign each task to only one machine to process.
  • At any time, a machine can process at most one task.
  • Task i (0 < i < n) can be processed if and only if each task j (0 < j < i) has been processed or processing.
  • If a task is processing on one machine, it cannot be interrupted.

You want to do finish all the tasks as soon as possible.

Input

There are multiple test cases. The first line of the input is an integer T (0 < T < 1000) indicating the number of test cases. Then T test cases follow. Each test case starts with an integer n (0 < n < 100). The ith line of the next n lines contains two integers tAtB (0 < tAtB < 100), giving the time to process the ith task by machine A and machine B.

Output

For each test case, output the earliest time when all the tasks have been processed.

Sample Input

4
1
1 2
2
1 2
2 1
2
1 2
90 95
3
1 3
1 3
1 3

Sample Output

1
1
90
3

Hints

  • Test case 1: Let machine A process task 1.
  • Test case 2: Let machine A process task 1 and at the same time let machine B process task 2.
  • Test case 3: Let machine B process task 1 and at the same time let machine A process task 2.
  • Test case 4: Let machine A process all the tasks.

Author: CAO, Peng
Solution: 
很有趣的双塔DP;

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <complex>
#include <algorithm>
#include <functional>
//#include <unordered_map>
#define ms(a) memset(a,0,sizeof(a))
#define rep(a,v,b) for(int a=v;a<b;a++)
#define pre(a,v,b) for(int a=v;a>b;a--)
typedef long long LL;
const LL LINF = LLONG_MAX;
const int INF = INT_MAX;
const int MAXN = 200 + 10;
const int MOD = 1000000009;
const double eps = 1e-7;
const double PI = acos(-1.0);
template <typename T>
T GCD(T a, T b)
{
	if (!b)return a;
	return GCD(b, a%b);
}
using namespace std;
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
/*(◕‿‿◕)  签订契约,成为马猴烧酒吧  (◕‿‿◕)*/
/*(◕‿‿◕)(◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕) (◕‿‿◕)*/
int ma[MAXN], mb[MAXN];
int dp[MAXN][MAXN];
int main()
{
	int N; cin >> N;
	while (N--)
	{
		int n; cin >> n;
		for (int i = 1; i <= n; i++)
			cin >> ma[i] >> mb[i];

		int offset = 100;
		for (int i = 0; i <= n; i++)
			for (int j = -100; j <= 100; j++)
				dp[i][j + offset] = INF;
		dp[0][0 + offset] = 0;

		for (int i = 1; i <= n; i++)
		{
			for (int j = -100; j <= 100; j++)
			{
				if (dp[i - 1][j + offset] == INF)continue;
				if (j > 0)
				{
					dp[i][ma[i] + offset] = min(dp[i][ma[i] + offset], dp[i - 1][j + offset] + ma[i]);
					if (j - mb[i] > 0)dp[i][j - mb[i] + offset] = min(dp[i][j - mb[i] + offset], dp[i - 1][j + offset]);
					else dp[i][j - mb[i] + offset] = min(dp[i][j - mb[i] + offset], dp[i - 1][j + offset] + mb[i] - j);
				}
				else
				{
					dp[i][-mb[i] + offset] = min(dp[i][-mb[i] + offset], dp[i - 1][j + offset] + mb[i]);
					if (j + ma[i] < 0)dp[i][j + ma[i] + offset] = min(dp[i][j + ma[i] + offset], dp[i - 1][j + offset]);
					else dp[i][j + ma[i] + offset] = min(dp[i][j + ma[i] + offset], dp[i - 1][j + offset] + ma[i] + j);
				}
			}
		}
		int ans = INF;
		for (int j = -100; j <= 100; j++)
			ans = min(ans, dp[n][j + offset]);
		printf("%d\n", ans);
	}
	return 0;
}

欢迎转载,请保留出处与链接。Ocrosoft » ZOJ 3331 Process the Tasks

点赞 (0)or拍砖 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址