题解

48 条题解

  • 4
    @ 2017-08-19 20:08:20

    最关键先压缩,然后就是最简单的背包了。

    这题数据水,如下压缩就行

    int hash1(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;
    }
    

    一开始直接定义叫hash,结果编译失败555

    完整代码如下

    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    int n,m,v[6],p[6],dp[5000004],ans=0;
    int hash1(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;
    }
    int main(){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&v[i]);
        for(int i=1;i<=n;i++){
            int x;
            scanf("%d",&x);
            for(int j=1;j<=m;j++)
                scanf("%d",&p[j]);
            for(int a=v[1];a>=p[1];a--){
                for(int b=v[2];b>=p[2];b--){
                    for(int c=v[3];c>=p[3];c--){
                        for(int d=v[4];d>=p[4];d--){
                            for(int e=v[5];e>=p[5];e--){
                                int y=hash1(a,b,c,d,e),z=hash1(a-p[1],b-p[2],c-p[3],d-p[4],e-p[5]);
                                dp[y]=max(dp[y],dp[z]+x);
                                ans=max(ans,dp[y]);
                            }
                        }
                    }
                }
            }
        }
        printf("%d",ans);
        return 0;
    }
    
  • 1
    @ 2019-08-08 17:47:23

    感谢大佬们的状态压缩思路。这里用循环代替了,能少很多时间。
    hash压缩后的值是可以直接相加的,因为是系数相加而已,这样少算一些。

    #include <iostream>
    
    using namespace std;
    
    int n,m;
    int v[5];
    int dp[5000000]={0};
    int pow;
    int th[5]={0};
    int tag[5];
    
    int ash(int *th)
    {
        int i,j;
        int ans=0;
        int temp;
        for(i=m-1;i>=0;i--)
        {
            temp=th[i];
            for(j=i+1;j<m;j++)
            {
                temp*=(v[j]+1);
            }
            ans+=temp;
        }
        return ans;
    }
    
    int main()
    {
        cin>>n>>m;
        int i,j,hax,now,ans=0;
        for(i=0;i<m;i++)
        {
            cin>>v[i];
        }
        for(i=0;i<n;i++)
        {
            cin>>pow;
            for(j=0;j<m;j++)
            {
                cin>>th[j];
            }
            hax=ash(th);
            for(tag[0]=v[0];tag[0]>=th[0];tag[0]--)
            for(tag[1]=v[1];tag[1]>=th[1];tag[1]--)
            for(tag[2]=v[2];tag[2]>=th[2];tag[2]--)
            for(tag[3]=v[3];tag[3]>=th[3];tag[3]--)
            for(tag[4]=v[4];tag[4]>=th[4];tag[4]--)
            {
                now=ash(tag);
                dp[now]=max(dp[now],dp[now-hax]+pow);
                ans=max(ans,dp[now]);
            }
        }
        cout<<ans<<endl;
        return 0;
    }
    
  • 0
    @ 2009-11-09 19:06:22

    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是每种药物的上限

    虽然不太清楚

    但hash很强

  • 0
    @ 2009-08-15 09:22:34

    很不解,太邪恶了!

  • 0
    @ 2009-08-07 15:20:32

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    感谢VIVID PUDDY 感谢LS的大牛

  • 0
    @ 2009-01-13 08:46:12

    ...

  • 0
    @ 2009-01-12 20:03:04

    我想问每个药品的提高值的范围是多少,如果范围足够小,那么可不可以把可能达到的提高值枚举出来再找最大?

  • 0
    @ 2008-12-25 19:50:59

    数据没有题目给出的那么可怕。。不加优化的背包就过了。。

    j:=hash(a1,b1,c1,d1,e1);

    k:=hash(a1-a,b1-a,c1-a,d1-a,e1-a);

    if s[k]+a>s[j] then s[j]:=s[k]+a;

    if s[j]>max then max:=s[j];

  • 0
    @ 2008-11-10 19:35:41

    Puppy

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Dragon

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Vijos Dolphin

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    终于过了

    程序 错误(一个数字打错) 的 时候 过了 六个点

    改过 之后 过 八个点 两个 超时

    然后 把 所有 过程 函数 都 去掉 就 全过了

    除了 状态压缩 之外 无其他优化

    tp:=0;

    for ll:=1 to m do

    tp:=tp+now[ll]*quan[ll];

    状态压缩。。。

    感谢 提供 压缩方案 的 大牛们。。。

    感谢 Puppy...

    没有它 我 过不了 的。。

    闪人。。

  • 0
    @ 2008-11-06 16:31:08

    请问下FUCK ME大牛,你是怎么做到0MS的,。。。不行的话,LYYZTT67说下好吗??? 小菜很膜拜了 ,。。。靠你们了

  • 0
    @ 2008-11-06 08:30:06

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    Vijos D 测的

    虽然和高兴是第一百个A的,但是这个时间惨不忍睹(最让我有怨念和愤怒的是我的哈希竟然一开始写错了……囧自己一个)

  • 0
    @ 2008-11-05 09:46:10

    这道题我用的o(200*5000000)的算法超时,应该怎么该?

  • 0
    @ 2008-11-04 20:12:18

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    这题的AC要感谢很多大牛的帮助:

    感谢:tianruiqi,414878523,linshutan以及hong,谢谢你们的照顾!

  • 0
    @ 2008-11-02 00:45:17

    编译通过...

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-10-28 18:56:13

    很疑惑我队列优化的压位为什么会错,答案都比正确答案大,光压位速度实在惨不忍睹。。有兴趣的朋友可以到 讨论 里 看我队列优化的程序,大牛知道哪里错了以后请发信息给我。。谢。

  • 0
    @ 2008-10-27 12:58:01

    终于知道状态压缩的意义了- -!!囧一个。。。。

  • 0
    @ 2008-10-20 11:30:10

    puppy啊..没你不行啊..

  • 0
    @ 2008-09-15 17:26:15

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    不用压缩照过........

  • 0
    @ 2008-09-08 23:46:53

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

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

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

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

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

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

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

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

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

    好丑的结果

    想问问楼下怎么优化的。。。

    我加了个很搓的优化。。。结果勉强通过

  • 0
    @ 2008-08-30 17:26:43

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

    队列优化

信息

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