P2577 [ZJOI2005]午餐

题目描述

上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。

THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。

现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。

假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。

现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。

输入输出格式

输入格式：

第一行一个整数N，代表总共有N个人。

以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。

输出格式：

一个整数T，代表所有人吃完饭的最早时刻。

输入输出样例

输入样例#1：复制

输出样例#1：复制

//一维数组    
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 0x3fffffff
#define maxn 10000

//dp[j]:代表第一个队伍排队总时间为j时的最晚集合时间
//（注意是第一个队伍！！！）
//第i个人选第一个队伍时：
//加入第一队进行的更新
//dp[j+p[i].a]=min(max(dp[j],j+p[i].b))
//加入第二队进行的更新
//dp[j]=max(dp[j],sum[i]-j+p[i].b)


struct node
{
    int a,b;
} p[1000];
int n;
int dp[400001];
int sum[1000];
int ans;

bool cmp(node x,node y)
{
    return x.b>y.b;
}

int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
        cin>>p[i].a>>p[i].b;
    sort(p+1,p+1+n,cmp);
    fill(&dp[0],&dp[400000],inf);
       dp[0]=0;
    for(int i=1; i<=n; i++)
        sum[i]=p[i].a+sum[i-1];
    for(int i=1; i<=n; i++)
        for(int j=sum[i]; j>=0; j--)
        {
            dp[j+p[i].a]=min(dp[j+p[i].a],max(dp[j],j+p[i].a+p[i].b));
            dp[j]=max(dp[j],sum[i]-j+p[i].b);
        }
    ans=inf;
    for(int i=1; i<=sum[n]; i++)
        ans=min(ans,dp[i]);
    cout<<ans;

    return 0;
}

//滚动数组
#include<cstdio>
#include<algorithm>
#include<cstring>
#define re register

using namespace std;

const int inf=0x3f3f3f3f;
const int N=205;

struct Goods
{
    int w,v;
    inline bool operator < (const Goods &rhs) const
    {
        return v>rhs.v;
    }
} a[N];
int n,sum[N],dp[2][N*N];
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d%d",&a[i].w,&a[i].v);
    sort(a+1,a+n+1);
    for(int i=1; i<=n; i++)
        sum[i]=sum[i-1]+a[i].w;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1; i<=n; i++)
    {
        re int cur=i&1,pre=cur^1;
//fill(&dp[cur][0],&dp[cur][N*N],inf);这么清空好些
        memset(dp[cur],127,sizeof(dp[cur]));//只清空了当前cur这一层
        for(int j=sum[i]; j>=0; j--)
        {
            if (j>=a[i].w)
                dp[cur][j]=min(dp[cur][j],max(dp[pre][j-a[i].w],j+a[i].v));
            dp[cur][j]=min(dp[cur][j],max(dp[pre][j],sum[i]-j+a[i].v));
        }
    }
    re int ans=inf;
    for(int i=0; i<=sum[n]; i++)
        ans=min(ans,dp[n&1][i]);
    printf("%d",ans);
    return 0;
}