/ Vijos / 题库 / 兴奋剂检查 /

题解

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
上传者
  1. 关于
  2. 联系我们
  3. 隐私
  4. 服务条款
  5. 版权申诉
  6. Language
  1. © 2005 - 2023 Vijos.org
  2. uibuild-2f1065f
  3. 沪ICP备14040537号-1