洛谷P1654 产品排序（sort）

P1654 产品排序（sort）

题目描述

有一系列产品，给定每个产品的加工时间和冷却成型时间（冷却过程产品之间没有关系，是单独冷却的）。现在你手上有两台机器可以用来加工，你需要安排产品加工的顺序以及去哪台机器加工，使得所有产品都成型的时间最早。机器之间互不相关，可以同时进行工作，一个机器一个时刻只能加工一个产品。

输入输出格式

输入格式：

第一行一个数n，表示产品个数，以下n行，每行两个数分别表示产品加工的时间A[i]和冷却时间B[i]。

【数据规模】

对于20%的数据，满足n≤6；

对于100%的数据，满足n,A[i],B[i]≤200。

输出格式：

一个数表示所有产品成型的最早时间。

输入输出样例

输入样例#1：

3

1 4

3 3

4 1

输出样例#1：

6

/*

    先贪心：按B从大到小排序

    再DP:设f[i][j]为前i个产品，A机器用时间j完成生产的最短时间，则有：

    f[i][j]=max(f[i-1][j-A[i]],j+B[i]);—给A机器生产

    f[i][j]=max(f[i-1][j],sum[i]-j+B[i]);—给B机器生产

    sum为排序后A[i]前缀和。

    上面俩取个min即可，注意下标越界，判一下即可。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 210

int n,ans;

bool vis[maxn];

int sum[maxn],dp[][];

struct node{

    int x,y;

    bool operator < (const node b)const{

        if(y!=b.y)return y>b.y;

    }

}a[maxn];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d",&a[i].x,&a[i].y);

    sort(a+,a+n+);

    for(int i=;i<=n;i++)sum[i]=sum[i-]+a[i].x;

    memset(dp,/,sizeof(dp));

    dp[][]=;

    for(int i=;i<=n;i++){

        for(int j=;j<=sum[i];j++){

            if(j>=a[i].x)dp[i][j]=min(dp[i][j],max(dp[i-][j-a[i].x],j+a[i].y));

            dp[i][j]=min(dp[i][j],max(dp[i-][j],sum[i]-j+a[i].y));

        }

    }

    int ans=0x7fffffff;

    for(int i=;i<=sum[n];i++)ans=min(ans,dp[n][i]);

    cout<<ans;

}