大致题意:
有两个机器a,b。要处理n个部件,第i个部件在机器a上完成需要atime[i],在b机器上需要btime[i],每个部件只能选择一个机器来完成。且当地i个部件开始加工时前[1,i-1]部件必须已经完成或者正在被加工。求加工完所有n个部件的最小时间是多少。
大致思路:
好神的dp,开始时乱想了几个状态都觉得不靠谱,膜拜了众犇的博客才明白怎么做,大神敬请bs。这里的状态表示非常奇怪。dp[i][j]代表的是,当加工到第i个部件,a机器比b机器的时间多出j+100时的最少时间是多少。
转移的时候就分别考虑当前任务放在a上或放在b上的最少时间分别是多少即可。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1<<28;
int dp[150][203];
int atime[150],btime[150];
int main()
{
int cas,i,j,n,m,ha,hb,ans;
cin>>cas;
while(cas--)
{
cin>>n;
for(i=1;i<=n;i++)
{
cin>>atime[i]>>btime[i];
}
for(i=0;i<=n;i++)
{
for(j=0;j<202;j++)
{
dp[i][j]=inf;
}
}
dp[0][100]=0;
for(i=1;i<=n;i++)
{
for(j=0;j<=200;j++)
{
if(dp[i-1][j]==inf)continue;
if(j<100)
{
ha=dp[i-1][j]-(100-j);
hb=dp[i-1][j];
}
else
{
ha=dp[i-1][j];
hb=dp[i-1][j]-(j-100);
}
if(j<100)
{
dp[i][ha+atime[i]-hb+100]=min(dp[i][ha+atime[i]-hb+100],max(dp[i-1][j],ha+atime[i]));
dp[i][100-btime[i]]=min(dp[i][100-btime[i]],dp[i-1][j]+btime[i]);
}
else
{
dp[i][ha-hb-btime[i]+100]=min(dp[i][ha-hb-btime[i]+100],max(dp[i-1][j],hb+btime[i]));
dp[i][100+atime[i]]=min(dp[i][100+atime[i]],dp[i-1][j]+atime[i]);
}
}
}
ans=inf;
for(i=0;i<=200;i++)
{
ans=min(ans,dp[n][i]);
}
cout<<ans<<endl;
}
return 0;
}
分享到:
相关推荐
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj 1610 Count the Colors.md
zoj题目简单归类zoj题目简单归类zoj题目简单归类
acm中zoj1002的可运行C++程序
zoj 1255 The Path.md
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 1810 The Gourmet Club.md
zoj 2499 The Happy Worm.md
zoj 2151 The Highest Profits.md
Problem Arrangement zoj 3777
ZOJ题目答案源码
一个非常非常非常非常实用的zoj结题代码
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
The reason is that when the director chooses the words from the dictionary and encrypts them, he never changes their order (the words in the dictionary are lexicographically sorted). String a1a2 ... ...
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
zoj1027解题指南和代码,还不错,是学校培训给的。
notes_for_zoj:打算转码的菜鸟,记录一下自己的刷题笔记〜
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·