热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU_3182_HamburgerMagi_状态压缩dp

HamburgerMagiTimeLimit:20001000MS(JavaOthers)MemoryLimit:3276832768K(JavaOthers)TotalSubmi

Hamburger Magi

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 509    Accepted Submission(s): 163


Problem Description
In the mysterious forest, there is a group of Magi. Most of them like to eat human beings, so they are called “The Ogre Magi”, but there is an special one whose favorite food is hamburger, having been jeered by the others as “The Hamburger Magi”.
Let’s give The Hamburger Magi a nickname “HamMagi”, HamMagi don’t only love to eat but also to make hamburgers, he makes N hamburgers, and he gives these each hamburger a value as Vi, and each will cost him Ei energy, (He can use in total M energy each day). In addition, some hamburgers can’t be made directly, for example, HamMagi can make a “Big Mac” only if “New Orleams roasted burger combo” and “Mexican twister combo” are all already made. Of course, he will only make each kind of hamburger once within a single day. Now he wants to know the maximal total value he can get after the whole day’s hard work, but he is too tired so this is your task now!
 
Input
The first line consists of an integer C(C<=50), indicating the number of test cases.
The first line of each case consists of two integers N,E(1<=N<=15,0<=E<=100) , indicating there are N kinds of hamburgers can be made and the initial energy he has.
The second line of each case contains N integers V1,V2…VN, (Vi<=1000)indicating the value of each kind of hamburger.
The third line of each case contains N integers E1,E2…EN, (Ei<=100)indicating the energy each kind of hamburger cost.
Then N lines follow, each line starts with an integer Qi, then Qi integers follow, indicating the hamburgers that making ith hamburger needs.
 
Output
For each line, output an integer indicating the maximum total value HamMagi can get.
 
Sample Input
1 4 90 243 464 307 298 79 58 0 72 3 2 3 4 2 1 4 1 1 0
 
Sample Output
298
 
做的第二道状态压缩dp。
状态压缩dp。虽然感觉不难,但是没能独立写出来。自己的代码估计是在关联的汉堡的处理上存在问题。
看了题解,很高兴基本套路没错,状态转移有问题(思路有问题)。
最后改为从后往前推,初始dp数组为-1,dp[0]=0,这样往后推,那么假如现在是dp[10100],处理到第5个汉堡,而第5个汉堡跟第1个和第3个相关联,那么在没有制作1和3时dp[10100]为-1,而为-1直接跳过,这样很好地处理了关联的问题。
技术分享技术分享
#include
#include
#include
#include
using namespace std;

struct Node
{
    int value;
    int cost;
    int cnt;
    int rela[20];
} ham[20];

struct Node1
{
    int value;
    int cost;
};
Node1 dp[1<<15];
int main()
{
    int t,kind,ener;
    scanf("%d",&t);
    while(t--)
    {
        memset(dp,-1,sizeof(dp));
        scanf("%d%d",&kind,&ener);
        for(int i=1; i<=kind; i++)
            scanf("%d",&ham[i].value);
        for(int i=1; i<=kind; i++)
            scanf("%d",&ham[i].cost);
        for(int i=1; i<=kind; i++)
        {
            scanf("%d",&ham[i].cnt);
            for(int j=0; j)
                scanf("%d",&ham[i].rela[j]);
        }
        int en=1<<kind;
        int ans=0;
        dp[0].cost=dp[0].value=0;
        for(int j=0; j)
        {
            if(dp[j].value==-1)
                continue;
            for(int i=1; i<=kind; i++)
            {
                int tem=1<<(kind-i);
                if(j&tem)
                    continue;
                int flag=1;
                for(int k=0; k)
                {
                    int temp=1<<(kind-ham[i].rela[k]);
                    if(!(temp&j))
                    {
                        flag=0;
                        break;
                    }
                }
                if(flag)
                {
                    dp[j+tem].value=dp[j].value+ham[i].value;
                    dp[j+tem].cost=dp[j].cost+ham[i].cost;
                }
            }
        }
        for(int i=0; i)
        {
            if(dp[i].cost>ener)
                continue;
            if(ans<dp[i].value)
                ans=dp[i].value;
        }
        printf("%d\n",ans);
    }
    return 0;
}
View Code

HDU_3182_Hamburger Magi_状态压缩dp


推荐阅读
  • 探讨 HDU 1536 题目,即 S-Nim 游戏的博弈策略。通过 SG 函数分析游戏胜负的关键,并介绍如何编程实现解决方案。 ... [详细]
  • 嵌入式开发环境搭建与文件传输指南
    本文详细介绍了如何为嵌入式应用开发搭建必要的软硬件环境,并提供了通过串口和网线两种方式将文件传输到开发板的具体步骤。适合Linux开发初学者参考。 ... [详细]
  • 深入理解Lucene搜索机制
    本文旨在帮助读者全面掌握Lucene搜索的编写步骤、核心API及其应用。通过详细解析Lucene的基本查询和查询解析器的使用方法,结合架构图和代码示例,带领读者深入了解Lucene搜索的工作流程。 ... [详细]
  • 在项目部署后,Node.js 进程可能会遇到不可预见的错误并崩溃。为了及时通知开发人员进行问题排查,我们可以利用 nodemailer 插件来发送邮件提醒。本文将详细介绍如何配置和使用 nodemailer 实现这一功能。 ... [详细]
  • C#设计模式学习笔记:观察者模式解析
    本文将探讨观察者模式的基本概念、应用场景及其在C#中的实现方法。通过借鉴《Head First Design Patterns》和维基百科等资源,详细介绍该模式的工作原理,并提供具体代码示例。 ... [详细]
  • 利用Selenium与ChromeDriver实现豆瓣网页全屏截图
    本文介绍了一种使用Selenium和ChromeDriver结合Python代码,轻松实现对豆瓣网站进行完整页面截图的方法。该方法不仅简单易行,而且解决了新版Selenium不再支持PhantomJS的问题。 ... [详细]
  • 深入解析动态代理模式:23种设计模式之三
    在设计模式中,动态代理模式是应用最为广泛的一种代理模式。它允许我们在运行时动态创建代理对象,并在调用方法时进行增强处理。本文将详细介绍动态代理的实现机制及其应用场景。 ... [详细]
  • 本文详细探讨了JavaScript中的作用域链和闭包机制,解释了它们的工作原理及其在实际编程中的应用。通过具体的代码示例,帮助读者更好地理解和掌握这些概念。 ... [详细]
  • Python 内存管理机制详解
    本文深入探讨了Python的内存管理机制,涵盖了垃圾回收、引用计数和内存池机制。通过具体示例和专业解释,帮助读者理解Python如何高效地管理和释放内存资源。 ... [详细]
  • 本文介绍如何使用MFC和ADO技术调用SQL Server中的存储过程,以查询指定小区在特定时间段内的通话统计数据。通过用户界面选择小区ID、开始时间和结束时间,系统将计算并展示小时级的通话量、拥塞率及半速率通话比例。 ... [详细]
  • 实用正则表达式有哪些
    小编给大家分享一下实用正则表达式有哪些,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下 ... [详细]
  • 解决TensorFlow CPU版本安装中的依赖问题
    本文记录了在安装CPU版本的TensorFlow过程中遇到的依赖问题及解决方案,特别是numpy版本不匹配和动态链接库(DLL)错误。通过详细的步骤说明和专业建议,帮助读者顺利安装并使用TensorFlow。 ... [详细]
  • 探索新一代API文档工具,告别Swagger的繁琐
    对于后端开发者而言,编写和维护API文档既繁琐又不可或缺。本文将介绍一款全新的API文档工具,帮助团队更高效地协作,简化API文档生成流程。 ... [详细]
  • Linux中的yum安装软件
    yum俗称大黄狗作用:解决安装软件包的依赖关系当安装依赖关系的软件包时,会将依赖的软件包一起安装。本地yum:需要yum源,光驱挂载。yum源:(刚开始查看yum源中的内容就是上图 ... [详细]
  • 深入理解ExtJS:从入门到精通
    本文详细介绍了ExtJS的功能及其在大型企业前端开发中的应用。通过实例和详细的文件结构解析,帮助初学者快速掌握ExtJS的核心概念,并提供实用技巧和最佳实践。 ... [详细]
author-avatar
mmakarlen
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有