[DP]zoj 3331：Process the Tasks

大致题意：
    有两个机器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;
}