HDU 4778 内存搜索&如压力

HDU 4778 内存搜索&如压力

大家好,又见面了,我是全栈君,今天给大家准备了Idea注册码。

鉴于G宝石,B包。和S。S当代表凑齐每种颜色的宝石S我们可以成为哲学家的石头

每个软件包包含N宝石。分别c1,c2…….

然后他们轮流拿包。每个包可以得到一次。宝石出包放在地上。

假设你可以成为魔法石拿着魔法石,次还这个人拿包。没变成则换人。
魔法石的个数就是获得分数,问两人最优的时候分差是多少。

状压记忆化搜索

一共21个包。状压存当前取包的状态

不管如何取,最后获得的魔法石数量一定

dp[i]表示在i状态下。先手能够获得的最高分数

#include "stdio.h"
#include "string.h"

int aim,g,b,s;
int dp[1<<22],c[25][10];
int bit[25];
int inf=0x3f3f3f3f;

int Max(int a,int b)
{
    if (a<b)return b;
    else return a;
}
int dfs(int cur,int sum,int temp[])
{
    int ans,i,next,j,w,cnt;
    int mark[10];
    if (cur==aim || sum==0) return 0;
    if (dp[cur]!=inf) return dp[cur];

    ans=0;
    for (i=1;i<=b;i++)
        if (cur&bit[i])
        {
            next=cur^bit[i];
            cnt=0;
            for (j=1;j<=g;j++)
            {
                mark[j]=temp[j]+c[i][j];
                cnt+=mark[j]/s;
                mark[j]%=s;
            }
            if (cnt>0) w=cnt+dfs(next,sum-cnt,mark);
            else w=sum-dfs(next,sum,mark);
            ans=Max(ans,w);
        }
    return dp[cur]=ans;
}
int main()
{
    int i,n,x,sum,aim,ans;
    int all[10],mark[25];
    bit[1]=1;
    for (i=2;i<=22;i++)
        bit[i]=bit[i-1]*2;

    while (scanf("%d%d%d",&g,&b,&s)!=EOF)
    {
        if (g+b+s==0) break;
        memset(c,0,sizeof(c));
        memset(all,0,sizeof(all));
        for (i=1;i<=b;i++)
        {
            scanf("%d",&n);
            while (n--)
            {
                scanf("%d",&x);
                c[i][x]++;
                all[x]++;
            }
        }
        sum=0;
        for (i=1;i<=g;i++)
            sum+=all[i]/s;

        aim=bit[b+1]-1;
        memset(mark,0,sizeof(mark));
        memset(dp,inf,sizeof(dp));
        ans=dfs(0,0,mark);
        printf("%d\n",ans-(sum-ans));
    }
    return 0;
}

版权声明:本文博主原创文章,博客,未经同意不得转载。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116934.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 网络号和主机号的计算

    网络号和主机号的计算网络号和主机号的计算当前使用的IP地址有4个字节(32)组成,即IPV4编码方式。每个IP地址包换两部分:网络号和主机号。当分配给主机号的二进制位越多,则能标识的主机数就越多,相应地能标识的网络数就越少,反之亦然。IP地址分为五类,A类保留给政府机构,B类分配给中等规模的公司,C类分配给任何需要的人,D类用于组播,E类用于实验,各类可容纳的地址数目不同。A、B、C三类IP地址的特征:当将IP…

  • python学习笔记——hashlib模块「建议收藏」

    python学习笔记——hashlib模块「建议收藏」上篇:https://blog.csdn.net/qq_42489308/article/details/89813895hashlibHash,译做“散列”,也有直接音译为“哈希”的。把任意长度的输入,通过某种hash算法,变换成固定长度的输出,该输出就是散列值,也称摘要值。该算法就是哈希函数,也称摘要函数。MD5是最常见的摘要算法,速度很快,生成结果是固定的16字节,通常用一个32…

  • phpstrom 激活码2021【在线破解激活】

    phpstrom 激活码2021【在线破解激活】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • c# 看门狗 程序_看门狗制作东西怎么切换

    c# 看门狗 程序_看门狗制作东西怎么切换C#制作简单的看门狗程序这个类实现了程序退出能重启,但是程序停止运行弹出对话框,进程并没有退出却无法重启。希望有好建议处理这个bug的朋友提出你们的宝贵意见。源码如下:usingSystem;usingSystem.Collections.Generic;usingSystem.Linq;usingSystem.Text;usingSystem.Diagnostics;usi

  • 贺州gdp排名末尾_xvesselgop

    贺州gdp排名末尾_xvesselgopGOP(GraphicOutputProtocol),是用来将图形驱动程序延伸至UEFI固件的接口,借以取代传统VBIOS(视讯BIOS)在开机资源要求等初始化行为。GOP与视讯BIOS

  • maven配置阿里云仓库镜像[通俗易懂]

    maven配置阿里云仓库镜像[通俗易懂]全局配置修改settting文件在mirrors标签下添加子节点。<mirror><id>nexus-aliyun</id><mirrorOf>central</mirrorOf><name>Nexusaliyun</name>…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号