前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >ZOJ 3331 Process the Tasks(双塔DP)

ZOJ 3331 Process the Tasks(双塔DP)

作者头像
ShenduCC
发布2018-04-26 17:18:26
4600
发布2018-04-26 17:18:26
举报
文章被收录于专栏:算法修养

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

代码语言:javascript
复制
4
1
1 2
2
1 2
2 1
2
1 2
90 95
3
1 3
1 3
1 3

Sample Output

代码语言:javascript
复制
1
1
90
3双塔DPdp[i][j] 表示执行第i个任务,机器A和机器B的时间差双塔DP 顾名思义可以把A机器和B机器看作是两座塔,如果把当前任务放在哪个塔上,那么哪个塔的高度就会增加每次放任务,都会有两个选择,要么放在A塔,要么放在B塔。如果放在高的塔上,根据题意在同一个机器上必要上一个任务完成时才能进行下一个任务,所以等高的塔完成上一个任务是,A,B都是空闲的了,这个是在高的塔上放任务,时间差就是这个任务的时间如果放在低的塔上,那么在之前的差值上加上这个任务的时间#include <iostream>
#include <string.h>
#include <stdlib.h>

#include <math.h>
#include <stdio.h>

using namespace std;
#define MAX 10000000
int dp[105][205];
int n;
int ta[105];
int tb[105];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
       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<=200;j++)
			   dp[i][j]=MAX;
	   dp[0][0+100]=0;
       for(int i=1;i<=n;i++)
	   {
		   for(int j=-99;j<=99;j++)
		   {
                 if(dp[i-1][j+100]==MAX)
					 continue;
				 if(j<0)
				 {
                     dp[i][-tb[i]+100]=min(dp[i][-tb[i]+100],dp[i-1][j+100]+tb[i]);
					 dp[i][j+ta[i]+100]=min(dp[i][j+ta[i]+100],dp[i-1][j+100]+max(0,j+ta[i]));
				 }
				 else
				 {
                     dp[i][ta[i]+100]=min(dp[i][ta[i]+100],dp[i-1][j+100]+ta[i]);
					 dp[i][j-tb[i]+100]=min(dp[i][j-tb[i]+100],dp[i-1][j+100]+max(0,tb[i]-j));
				 }
		   }
	   }
	   int ans=MAX;
	   for(int i=-99;i<=99;i++)
		   ans=min(ans,dp[n][i+100]);
	   printf("%d\n",ans);
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-05-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档