[ZJOI2004]午餐
题目描述
上午的训练结束了，THU ACM小组集体去吃午餐，他们一行N人来到了著名的十食堂。这里有两个打饭的窗口，每个窗口同一时刻只能给一个人打饭。由于每个人的口味（以及胃口）不同，所以他们要吃的菜各有不同，打饭所要花费的时间是因人而异的。另外每个人吃饭的速度也不尽相同，所以吃饭花费的时间也是可能有所不同的。
THU ACM小组的吃饭计划是这样的：先把所有的人分成两队，并安排好每队中各人的排列顺序，然后一号队伍到一号窗口去排队打饭，二号队伍到二号窗口去排队打饭。每个人打完饭后立刻开始吃，所有人都吃完饭后立刻集合去六教地下室进行下午的训练。
现在给定了每个人的打饭时间和吃饭时间，要求安排一种最佳的分队和排队方案使得所有人都吃完饭的时间尽量早。
假设THU ACM小组在时刻0到达十食堂，而且食堂里面没有其他吃饭的同学（只有打饭的师傅）。每个人必须而且只能被分在一个队伍里。两个窗口是并行操作互不影响的，而且每个人打饭的时间是和窗口无关的，打完饭之后立刻就开始吃饭，中间没有延迟。
现在给定N个人各自的打饭时间和吃饭时间，要求输出最佳方案下所有人吃完饭的时刻。
输入格式
第一行一个整数N，代表总共有N个人。
以下N行，每行两个整数 Ai，Bi。依次代表第i个人的打饭时间和吃饭时间。
输出格式
一个整数T，代表所有人吃完饭的最早时刻。
样例 #1
样例输入 #1
5
2 2
7 7
1 3
6 4
8 5
样例输出 #1
17
提示
所有输入数据均为不超过200的正整数。
思路
首先我们知道 我们贪心的按照Bi排序 这样肯定是最优解（只有一行的情况下）
而我们转化成两行 无非就是在一行中抽出 一些 那就是选与不选 这里就很像我们的背包
我们直接dp即可
我们设dp[i][j]为当前到了第i个人 我们第1个窗口的打饭时间为j 的前i个人吃完饭的最早时刻。
因为我们答案要的就是时间所以第二维不需要枚举有多少人 直接枚举多少人构成的时间即可
然后就是我们的状态转移：
我们把ai放在第一号窗口
dp[i][j]=min(dp[i][j],max(dp[i-1][j-a[i]],j+b[i])
我们把ai放在第二号窗口
dp[i][j]=min(dp[i][j],max(dp[i-1][j],j-sum[i]+b[i]));
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[210][40010];
void solve() {
int n;cin>>n;
pair<int,int>a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i].second>>a[i].first;
}
sort(a+1,a+n+1,greater<>());
vector<int>s(n+1);
for(int i=1;i<=n;i++){
s[i]+=s[i-1]+a[i].second;
}
int mn=INF;
memset(dp,0x3f3f,sizeof dp);
dp[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=s[i];j++){
if(j>=a[i].second)dp[i][j]=min(dp[i][j],max(dp[i-1][j-a[i].second],j+a[i].first));
dp[i][j]=min(dp[i][j],max(dp[i-1][j],s[i]-j+a[i].first));
if(i==n)mn=min(mn,dp[i][j]);
}
}
cout<<mn<<endl;
}
signed main(){
fast
int T;T=1;
while(T--) {
solve();
}
return ~~(0^_^0);
}