热门标签 | 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


推荐阅读
  • 本文详细介绍了 Windows API 中的按钮控件及其应用实例。主要功能包括:1. `CheckDlgButton` 用于更改对话框中按钮的选中状态;2. `CheckRadioButton` 用于设置单选按钮的选中状态。此外,还探讨了按钮控件在实际开发中的多种应用场景,帮助开发者更好地理解和使用这些功能。 ... [详细]
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 利用树莓派畅享落网电台音乐体验
    最近重新拾起了闲置已久的树莓派,这台小巧的开发板已经沉寂了半年多。上个月闲暇时间较多,我决定将其重新启用。恰逢落网电台进行了改版,回忆起之前在树莓派论坛上看到有人用它来播放豆瓣音乐,便萌生了同样的想法。通过一番调试,终于实现了在树莓派上流畅播放落网电台音乐的功能,带来了全新的音乐享受体验。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • 通过 NuGet 获取最新版本的 Rafy 框架及其详细文档
    为了帮助开发者更便捷地使用Rafy领域实体框架,我们已将最新版的Rafy框架程序集上传至nuget.org,并同步发布了最新版本的Rafy SDK至Visual Studio。此外,我们还提供了详尽的文档和示例,以确保开发者能够快速上手并充分利用该框架的强大功能。 ... [详细]
  • 虚拟机网络设置与数据库远程连接优化指南
    本文针对个人计算机上虚拟机网络配置与数据库远程连接的问题,提供了一套详细的优化指南。在探讨远程数据库访问前,需确保网络配置正确,特别是桥接模式的设置。通过合理的网络配置,可以有效解决因虚拟机或网络问题导致的连接失败,提升远程访问的稳定性和效率。 ... [详细]
  • 在 Angular Google Maps 中实现图片嵌入信息窗口的功能,可以通过使用 `@agm/core` 库来实现。该库提供了丰富的 API 和组件,使得开发者可以轻松地在地图上的信息窗口中嵌入图片。本文将详细介绍如何配置和使用这些组件,以实现动态加载和显示图片的功能。此外,还将探讨一些常见的问题和解决方案,帮助开发者更好地集成这一功能。 ... [详细]
  • 在 Vue 项目中,为了提高页面加载速度和优化用户体验,实现图片上传前的压缩处理至关重要。本文介绍了如何通过集成第三方库和自定义组件,有效减小图片文件大小,确保在不影响图像质量的前提下,提升应用性能。 ... [详细]
  • 二叉树的直径是指树中任意两个叶节点之间最长路径上的节点数量。本文深入解析了计算二叉树直径的算法,并提出了一种优化方法,以提高计算效率和准确性。通过详细的案例分析和性能对比,展示了该优化算法在实际应用中的优势。 ... [详细]
  • 本文全面解析了 gRPC 的基础知识与高级应用,从 helloworld.proto 文件入手,详细阐述了如何定义服务接口。例如,`Greeter` 服务中的 `SayHello` 方法,该方法在客户端和服务器端的消息交互中起到了关键作用。通过实例代码,读者可以深入了解 gRPC 的工作原理及其在实际项目中的应用。 ... [详细]
  • 在Python网络编程中,多线程技术的应用与优化是提升系统性能的关键。线程作为操作系统调度的基本单位,其主要功能是在进程内共享内存空间和资源,实现并行处理任务。当一个进程启动时,操作系统会为其分配内存空间,加载必要的资源和数据,并调度CPU进行执行。每个进程都拥有独立的地址空间,而线程则在此基础上进一步细化了任务的并行处理能力。通过合理设计和优化多线程程序,可以显著提高网络应用的响应速度和处理效率。 ... [详细]
  • 如何高效启动大数据应用之旅?
    在前一篇文章中,我探讨了大数据的定义及其与数据挖掘的区别。本文将重点介绍如何高效启动大数据应用项目,涵盖关键步骤和最佳实践,帮助读者快速踏上大数据之旅。 ... [详细]
  • 本文详细介绍了 jQuery 的入门知识与实战应用,首先讲解了如何引入 jQuery 库及入口函数的使用方法,为初学者提供了清晰的操作指南。此外,还深入探讨了 jQuery 在实际项目中的多种应用场景,包括 DOM 操作、事件处理和 AJAX 请求等,帮助读者全面掌握 jQuery 的核心功能与技巧。 ... [详细]
  • CentOS 7环境下Jenkins的安装与前后端应用部署详解
    CentOS 7环境下Jenkins的安装与前后端应用部署详解 ... [详细]
  • 在处理大图片时,PHP 常常会遇到内存溢出的问题。为了避免这种情况,建议避免使用 `setImageBitmap`、`setImageResource` 或 `BitmapFactory.decodeResource` 等方法直接加载大图。这些函数在处理大图片时会消耗大量内存,导致应用崩溃。推荐采用分块处理、图像压缩和缓存机制等策略,以优化内存使用并提高处理效率。此外,可以考虑使用第三方库如 ImageMagick 或 GD 库来处理大图片,这些库提供了更高效的内存管理和图像处理功能。 ... [详细]
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社区 版权所有