题解

35 条题解

  • 1
    @ 2017-08-02 16:27:32
    #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);
        }
    }
    
  • 0
    @ 2009-10-07 23:21:03

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

    但两个窗口不会处理

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

    忽然想到 sum 问题迎刃而解

  • 0
    @ 2009-09-10 21:38:13

    可以证明,同组内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同理。

  • 0
    @ 2009-08-14 19:11:46

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

    用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

  • 0
    @ 2009-07-21 19:14:27

    编译通过...

    ├ 测试数据 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题!

  • 0
    @ 2009-06-13 19:43:06

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

  • 0
    @ 2009-06-09 19:54:55

    嘿嘿,我神牛把?这题被我神牛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]

  • 0
    @ 2009-06-07 08:55:53

    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
    @ 2013-04-03 23:17:13

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

  • -1
    @ 2009-11-04 09:24:24

    庆祝200题

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

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

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

  • -1
    @ 2009-10-13 10:00:54

    编译通过...

    ├ 测试数据 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

  • -1
    @ 2009-10-08 11:46:27

    唉。。我蒟蒻

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

    可是DP。。

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

    看来我得加油了

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

  • -1
    @ 2009-09-20 16:31:21

    好BT的DP方程……

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

  • -1
    @ 2009-09-20 14:35:35

    有点类似矿工配餐

  • -1
    @ 2009-09-07 21:06:08

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

    可惜没秒杀

  • -1
    @ 2009-09-07 20:15:49

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

  • -1
    @ 2009-08-07 11:05:30

    [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!

  • -1
    @ 2009-08-07 09:28:25

    编译通过...

    ├ 测试数据 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秒杀

  • -1
    @ 2009-07-23 21:27:42

    原来10分是这个原因……

  • -1
    @ 2009-07-15 13:31:10

    THU!!!尽管我想上PKU,还是先Orz一下

信息

ID
1551
难度
6
分类
其他 | 二分查找贪心 | 动态规划 点击显示
标签
(无)
递交数
558
已通过
163
通过率
29%
被复制
2
上传者