#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

struct p_1
{
    int a,b;
}a[200+1];

int n;
int b[200+1];
int f[200+1][200*200+1];

bool cmp_p_1(p_1 x,p_1 y)
{
    return x.b>y.b;
}

int main()
{
    while (~scanf("%d",&n))
    {
        for (int i=1;i<=n;i++)
            scanf("%d%d",&a[i].a,&a[i].b);
        sort(&(a[1]),&(a[n+1]),cmp_p_1);
        memset(b,0,sizeof(b));
        for (int i=1;i<=n;i++)
            b[i]=b[i-1]+a[i].a;
        memset(f,oo_max,sizeof(f));
        f[0][0]=0;
        for (int i=1;i<=n;i++)
            for (int j=0;j<=b[i-1];j++)
            {
                f[i][j]=min(f[i][j],max(f[i-1][j],b[i-1]-j+a[i].a+a[i].b));
                f[i][j+a[i].a]=min(f[i][j+a[i].a],max(f[i-1][j],j+a[i].a+a[i].b));
            }
        int ans=oo_max;
        for (int i=0;i<=b[n];i++)
            ans=min(ans,f[n][i]);
        printf("%d\n",ans);
    }
}

看到这题马上想到排序后背包

但两个窗口不会处理

2维暴空间,1维怎么弄呢????

忽然想到 sum 问题迎刃而解

可以证明，同组内B递降。

令Xi=Ai,Yi=Bi

对于同一窗口相邻的两个人i j(ixi+yi且xj+xj+yj显然大于后式，所以得证。

题外：这个规律不好发现，最好写搜索打出最优方案以后再来看规律。

f[i][j][k]表示到了第I个人，第1/2个窗口已经累计了J的时间。

则有

当k=0时

c1=max(f[j+a[i]][k],j+a[i]+b[i]);选择第一个窗口;

考虑选择第二个窗口：

当a[i]j时：

c3=max(f[a[i]-j][k xor 1]+j,a[i]+b[i]);

f[i][j][k]=min(c1,c2,c3);

k=1同理。

其实这道题很简单，说说我的思路吧。

用f表示到第i个点，在第一口累计打饭时间为j,在两口中

时间比较小的口的大小。

于是f:=min{max(f,j+b[i])}(第i点在第一口打饭）

{max(f,d[i]-j+b[i])}（第i点在第二口打饭）

d[i]表示1到i点累计打饭时间。a[i]是打饭时间。b[i]是吃饭时间。

我想以我的方法都可以轻松0ms秒杀

还是不懂可以联系我。qq:983030491

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

yeach~~~~~~~~

终于AC了，哈哈，耗时0ms，最快是我！

我的思想跟那个假冒的陶××不同，比他那个更难理解，但效率高。

但本人极菜～～～～说不清楚。请见谅。

一开始我发现这问题极像搭建双塔那题，但又些不同，我把它修改了一下

首先要证明一下：

如样例：最小为17，不知大家有没有发现这个17=7+6+2+2，最后一个二是那一列的bi里最小的，而且17>8+3+1=12，所以把问题转为把数分成两组，找出所有高塔中的最小的塔，就是答案。可以证明17是所有高塔中最小的了。

轮到主角了。

转移方程为：

if(f[j]!=-1)

f[i][j+a[i]]=f[j]+a[i],放在高塔上

.....

放低塔上就自己写吧，反正大家都会。

但要注意一个很重要的问题

就是我们的bi，怎样保存当前列最小的bi，大家各自想把，说白了就没意思。

我是把它都整合在f[i][j]=z里了，这样可以省很多空间。

不明白就想明白吧，反正我比你还菜，才过了11题！

Orz 某个叫做陶XX的……想当年我都没这么自恋过……

嘿嘿，我神牛把？这题被我神牛AC了！！！

大家快来膜拜我！！！！！！

大家说我是不是神牛？

既然我这么神牛，那神牛我就教教大家菜鸟们怎么做吧。

首先，我们很容易知道吃饭时间长的应该放在前面。（这点证明很容易）

然后，我们将所有人按吃饭时间从大到小排序，接着就能DP了。

我们先解释一下状态的表示：

我们设f表示第i~n个人去打饭吃饭。

显然，总的所需时间=在第一个窗口所花时间与在第二个窗口所花时间的最大值。

这里的所花时间包括吃饭的时间。

我们假定我们在第1个窗口所花的时间小于等于j

那么，我们在第2个窗口至少花的时间就记作f

状态转移方程：

f= ①如果第i个人去第2个窗口吃饭：max(f+A[i],A[i]+B[i])

②如果第i个人去第1个窗口吃饭：f (条件：A[i]+b[i]

Orz cgy

这个方程,说出来就没意思了

可以明确的一点是

吃饭时间长肯定要比吃饭时间短的先打饭

给个弱弱的证明:

X1,X2两人打饭时间分别是A1,A2,吃饭时间分别为C1,C2,且C1>C2;

设之前已耗时T(这里的比较是考虑X1,X2在同一窗口打饭)

若X1先打,则耗时TA=MAX(T+A1+C1(记为T1),T+A1+A2+C2(记为T2))

若X2先打,则耗时TB=MAX(T+A2+C2(记为T3),T+A2+A1+C1(记为T4))

因为T4-T3=C1+A1-C2>0

所以TB=T4;

显然有T2

1.**orz**
2.**orz**

庆祝200题

f表示前i个人在一号打饭时间为j的总时间最小值

f=min{max{f,s[i]-j+b[i]}, (在二号打饭)

max{f}} (在一号打饭)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 103ms

├ 测试数据 08：答案正确... 103ms

├ 测试数据 09：答案正确... 72ms

├ 测试数据 10：答案正确... 41ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：319ms

...

不是DP

....

RP算法

当然贪心还是要的

for ii:=1 to 50000 do

begin

k:=random(n)+1;

if b[k]=0 then b[k]:=1 else b[k]:=0;

chi[0]:=0;

chi[1]:=0;

tt[0]:=0;

tt[1]:=0;

for i:=1 to n do

begin

tt[b[i]]:=tt[b[i]]+a[i].x;

if chi[ b[i] ]-a[i].x

唉。。我蒟蒻

吃饭时间递减的贪心是推出来了。。

可是DP。。

没想到还可以这样做。而且还倒着做

看来我得加油了

orz curimit、山寨版陶文博、fjxmlhx等神牛

好BT的DP方程……

Orz陶文博大牛、宋文杰大牛.

有点类似矿工配餐

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 41ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：138ms

可惜没秒杀

吃饭时间久的先打饭。。。然后DP同楼下

[blue]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 56ms

├ 测试数据 08：答案正确... 56ms

├ 测试数据 09：答案正确... 56ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

[red]

Accepted 有效得分：100 有效耗时：177ms

秒杀牛orz!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 72ms

├ 测试数据 08：答案正确... 88ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

200^3 居然过了，倒者dp好处理多了，

一次ac,没想到！

[red]

遗憾没0ms秒杀

原来10分是这个原因……

THU！！！尽管我想上PKU，还是先Orz一下