题解

48 条题解

  • 0
    @ 2008-08-28 10:19:13

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    把f[i1][i2][i3][i4][i5]五维背包换成f[5000000],做一个函数hash:

    int hash(int a,int b,int c,int d,int e)

    {

    return a*(v[2]+1)*(v[3]+1)*(v[4]+1)*(v[5]+1)+b*(v[3]+1)*(v[4]+1)*(v[5]+1)+c*(v[4]+1)*(v[5]+1)+d*(v[5]+1)+e;

    }

  • 0
    @ 2008-08-25 19:46:21

    思想同hash。

    全局可能的状态数极多,但单个测试点的状态数较少。

    用秦九韶小小优化一下hash的代码:

    hash := (((i5*(v[4]+1)+i4)*(v[3]+1)+i3)*(v[2]+1)+i2)*(v[1]+1)+i1;

  • 0
    @ 2008-08-24 22:19:52

    楼下同志,发题解程序小心号封锁。现在不同原来了...

  • 0
    @ 2008-08-23 16:49:31

    状态压缩.

    下标取:i1+i2*(v1+1)+i3*(v1+1)*(v2+1)+i4*(v1+1)*(v2+1)*(v3+1)+i5*(v1+1)*(v2+1)*(v3+1)*(v4+1)

    i1,i2,i3,i4,i5是5种药的量

    v1,v2,v3,v4,v5是每种药物的上限

  • 0
    @ 2008-08-23 15:39:44

    给每种不同的包的组合编一个唯一的号即可 数组稍微开大一点 因为考虑包的容积可以为0

  • 0
    @ 2008-08-23 13:38:56

    背包

  • 0
    @ 2008-08-23 13:15:01

    问一下,为什么按那样用二进制顺次连接起来的totv就不会超过5000000?这是很明显可以超过的,而且按照不同的顺序得到的totv会不一样。

    不过二进制的思想是不错的,拍了一会过了。

    standard里面的背包貌似是可重复的(难道我看错了?)

  • 0
    @ 2008-08-23 18:22:13

    那个5000000是其实虚指……但是到考试中也可能是m很大但是n很小,这就是数据范围=。=

    =。=

    正因为小于5000000所以我才说是小于5000000,具体得估计比500000还要小……

    二进制是为了编码实现要简便点,看着也很爽……

    如果是可重复背包那我的程序就错了……

  • 0
    @ 2008-08-25 23:13:44

    楼下的....那样子可以压成一个数,但是怎么压回来?

  • 0
    @ 2008-08-23 09:56:45

    这怎么背包 数组要多大!!!

  • 0
    @ 2008-08-23 00:26:07

    rqnoj的题

    也是那次模拟赛我唯一ac的题....

  • 0
    @ 2008-08-22 23:56:25

    背包问题

    今天太晚了,第一又被抢走了明天来A

  • 0
    @ 2008-08-25 14:43:45

    状态压缩,把500W的空间彻底利用起来

  • -1
    @ 2013-10-26 17:04:20

    居然__*一次*__就过了

  • -1
    @ 2013-10-18 22:14:38

    记录信息
    评测状态 Accepted
    题目 P1426 兴奋剂检查
    递交时间 2013-10-18 22:12:30
    代码语言 C++
    评测机 上海红茶馆
    消耗时间 1216 ms
    消耗内存 39708 KiB
    评测时间 2013-10-18 22:12:32

    评测结果
    编译成功

    测试数据 #0: Accepted, time = 31 ms, mem = 39708 KiB, score = 11

    测试数据 #1: Accepted, time = 78 ms, mem = 39708 KiB, score = 11

    测试数据 #2: Accepted, time = 468 ms, mem = 39704 KiB, score = 11

    测试数据 #3: Accepted, time = 359 ms, mem = 39708 KiB, score = 11

    测试数据 #4: Accepted, time = 109 ms, mem = 39708 KiB, score = 11

    测试数据 #5: Accepted, time = 109 ms, mem = 39708 KiB, score = 11

    测试数据 #6: Accepted, time = 31 ms, mem = 39708 KiB, score = 11

    测试数据 #7: Accepted, time = 31 ms, mem = 39704 KiB, score = 11

    测试数据 #8: Accepted, time = 0 ms, mem = 39708 KiB, score = 12

    Accepted, time = 1216 ms, mem = 39708 KiB, score = 100

    代码
    #include <iostream>
    using namespace std;
    int a1,a2,a3,a4,a5;
    int j,k;
    int ans,m,n;
    int a[10000001];
    int b[201][6];
    int f[6];
    int main()
    {
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
    cin>>f[i];
    }
    for (int i=1;i<=n;i++)
    for (int j=0;j<=m;j++)
    cin>>b[i][j];
    for (int i=1;i<=n;i++)
    for (a1=f[1];a1>=b[i][1];a1--)
    for (a2=f[2];a2>=b[i][2];a2--)
    for (a3=f[3];a3>=b[i][3];a3--)
    for (a4=f[4];a4>=b[i][4];a4--)
    for (a5=f[5];a5>=b[i][5];a5--)
    {
    j=(((a1*(f[2]+1)+a2)*(f[3]+1)+a3)*(f[4]+1)+a4)*(f[5]+1)+a5;
    k=((((a1-b[i][1])*(f[2]+1)+(a2-b[i][2]))*(f[3]+1)+(a3-b[i][3]))*(f[4]+1)+(a4-b[i][4]))*(f[5]+1)+a5-b[i][5];
    if (a[k]+b[i][0]>a[j])
    {
    a[j]=a[k]+b[i][0];
    if (a[j]>ans) ans=a[j];
    }
    }
    cout<<ans<<endl;
    return 0;
    }

  • -1
    @ 2012-11-09 09:47:07

    编译通过... 

    ├ 测试数据 01:答案正确... (31ms, 39412KB) 

    ├ 测试数据 02:答案正确... (94ms, 39408KB) 

    ├ 测试数据 03:答案正确... (546ms, 39408KB) 

    ├ 测试数据 04:答案正确... (421ms, 39408KB) 

    ├ 测试数据 05:答案正确... (141ms, 39412KB) 

    ├ 测试数据 06:答案正确... (156ms, 39412KB) 

    ├ 测试数据 07:答案正确... (63ms, 39412KB) 

    ├ 测试数据 08:答案正确... (63ms, 39412KB) 

    ├ 测试数据 09:答案正确... (0ms, 39408KB) 

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

    Accepted / 100 / 1518ms / 39412KB 

    view sourceprint?

    01

    #include

    02

    using namespace std;

    03

    int a1,a2,a3,a4,a5;

    04

    int j,k;

    05

    int ans,m,n;

    06

    int a[10000001];

    07

    int b[201][6];

    08

    int f[6];

    09

     

    10

     

    11

     

    12

     

    13

     

    14

     

    15

     

    16

     

    17

     

    18

     

    19

     

    20

     

    21

    int main()

    22

    {

    23

        cin>>n>>m;

    24

        for (int i=1;i>f[i];

    27

        }

    28

        for (int i=1;ib[i][j];

    31

        for (int i=1;i=b[i][1];a1--)

    33

                for (a2=f[2];a2>=b[i][2];a2--)

    34

                    for (a3=f[3];a3>=b[i][3];a3--)

    35

                        for (a4=f[4];a4>=b[i][4];a4--)

    36

                            for (a5=f[5];a5>=b[i][5];a5--)

    37

                            {

    38

                                j=(((a1*(f[2]+1)+a2)*(f[3]+1)+a3)*(f[4]+1)+a4)*(f[5]+1)+a5;

    39

                                k=((((a1-b[i][1])*(f[2]+1)+(a2-b[i][2]))*(f[3]+1)+(a3-b[i][3]))*(f[4]+1)+(a4-b[i][4]))*(f[5]+1)+a5-b[i][5];

    40

                                if (a[k]+b[i][0]>a[j])

    41

                                {

    42

                                    a[j]=a[k]+b[i][0];

    43

                                    if (a[j]>ans) ans=a[j];

    44

                                }

    45

                            }

    46

        cout

  • -1
    @ 2009-09-24 12:47:51

    晕菜

    不会 怎么压的?

    哪位牛指导一下~~~~~

    QQ:392106999 谢谢!

  • -1
    @ 2009-09-21 11:08:58

    一不小心..

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    就ac了.

  • -1
    @ 2009-09-20 16:56:04

    哪个大牛能解释一下,为什么HASH压缩不会冲突。

    PS:感谢PUPPY

  • -1
    @ 2009-09-20 14:50:33

    编译通过...

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

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

    ├ 测试数据 03:运行超时...

    ├ 测试数据 04:运行超时...

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

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

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

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

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

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

    Unaccepted 有效得分:78 有效耗时:2431ms

    Flag   Accepted

    题号   P1426

    类型(?)   动态规划

    通过   163人

    提交   817次

    通过率   20%

    难度   2

    ???

    什么都没改再来一次

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

信息

ID
1426
难度
6
分类
动态规划 | 状态压缩DP动态规划 | 背包 点击显示
标签
递交数
994
已通过
253
通过率
25%
被复制
3
上传者