一起去打CS（codevs 5059）

题目描述 Description

早就和lyk约好了去打cs，一直没找着时间，终于今天我家没人，他家也没人，总算可以出去了。但是偏偏天公不作美，某某人非要留那么多题要做。没办法只能尽快做完然后抓紧时间吧……

为了尽量节省时间，我俩决定分开做所有题吧（嘿嘿，稍微耍一下滑~~）。但是有的题我比较擅长，而有的题lyk要比我做的快。所以为了尽快做完所有的题，我们要好好的分配一下。现在给出你要做题 的数目和我俩分别做每个题所需要的时间。希望你帮忙计算一下，我们最少需要多长时间才能做完所有的题去打cs啊！！！

输入描述 Input Description

第一行一个正整数n，表示有n个题要做。

接下来有n行，每行两个正整数ai，bi。 分别表示我和lyk做每个题所用的时间。

输出描述 Output Description

一个数，最少需要多长时间才能去打CS。

样例输入 Sample Input

3

5 10

6 11

7 12

样例输出 Sample Output

12

数据范围及提示 Data Size & Hint

30%的数据满足：1 <= n <= 20

100%的数据满足：1 <= n <= 200 , 1 <= ai,bi <=200

/*

  第一遍做用vijos搭建双塔三维数组的方法做的，尽管哑了第一维，但还是MLE了

  然后看了看题解，是用01背包的方法做的，

*/

#include<cstdio>

#include<iostream>

#include<cstring>

#define M 210

using namespace std;

int f[][M*M],a[M],b[M],n,m;

int main()

{

    freopen("jh.in","r",stdin);

    memset(f,0x3f3f3f3f,sizeof(f));

    scanf("%d",&n);

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

    {

        scanf("%d%d",&a[i],&b[i]);

        m+=max(a[i],b[i]);

    }

    f[][]=;

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

    {

        for(int j=;j<=m;j++)

          if(j>=a[i])

            f[i%][j]=min(f[(i+)%][j-a[i]],f[(i+)%][j]+b[i]);

          else f[i%][j]=f[(i+)%][j]+b[i];

        for(int j=;j<=m;j++)

          f[(i+)%][j]=0x3f3f3f3f;

    }

    int ans=m;

    for(int i=;i<=m;i++)

      ans=min(ans,max(f[n%][i],i));

    printf("%d",ans);

    return ;

}