Hdoj-1074-状压dp_hdoj 1074-程序员宅基地

技术标签: dp  

n个课程就是一个有n位置的二进制数,然后从0(也就是还没写作业)到(1<< n)-1(也就是全写完DP求最优解)
比如说 要完成四门作业的话此时要推dp[1011](第1,2,4门作业完成最少扣得分)那它就是由 dp[1001],dp[0011],dp[1010]三个状态转移的最优解,
置于顺序输出则先由0011转移再由1001转移再由1010转移(物品从n-1到0进行选取也就是先把下表大的作业去掉)

#include<cstdio>
#include<string>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
struct node{
   int time,score,past;
}dp[1<<20];
struct cl{
   int  li,fin;
    string name;
}a[100];
int n;
int main()
{
    int t;
    scanf("%d",&t);
   while(t--)
   {
         scanf("%d",&n);
         for(int i=0;i<n;i++)
           cin>>a[i].name>>a[i].li>>a[i].fin;
         int n1 = (1<<n)-1;
         dp[0].time = 0;
         dp[0].score = 0;
         dp[0].past = 0;
         for(int i=1;i<=n1;i++)//DP
       {
               dp[i].score = 0x7ffffff;
                 for(int j=n-1;j>=0;j--)//保证顺序输出
                 {
                      if(i&(1<<j)){
                              int past = i-(1<<j);
                                int ans = dp[past].time+a[j].fin-a[j].li;
                                int ma = ans>0?  ans:0;
                                if(dp[past].score+ma<dp[i].score){
                                     dp[i].score = dp[past].score + ma;
                                     dp[i].past = past;
                                     dp[i].time = dp[past].time+a[j].fin;
                                }
                        }   
                 }
         }
         printf("%d\n",dp[n1].score);
         stack<int>st;
         int pre = n1;
         while(pre)
         {
              st.push(pre-dp[pre].past);
              pre = dp[pre].past;
         }
         while(!st.empty())
         {
               int ans = st.top(),i1 = 0;
               st.pop();
                 while(ans){
                     i1++;
                     ans>>=1;
                 }
               cout<<a[i1-1].name<<endl;
         }
     }
  return 0;
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/acblacktea/article/details/50905494

智能推荐

【Echarts】echarts tooltip小箭头,及阴影样式修改,双Y轴显示,折线图和柱状图同时展示,legend分开展示_echarts tooltip 箭头-程序员宅基地

文章浏览阅读7k次。this.circleChart = { tooltip: { trigger: 'item', backgroundColor: '#fff', textStyle: { color: '#666', ..._echarts tooltip 箭头

java scriptengine,使用Java ScriptEngine(Groovy),如何使它更具性能?-程序员宅基地

文章浏览阅读1.1k次。I am using ScriptEngine in my app to evaluate some client code in my application.The problem is it's not performant enough and I need to take measures to improve the time of execution.Currently, it ca..._scriptenginemanager 性能优化

msys2 环境配置记录-程序员宅基地

文章浏览阅读968次。命令行添加镜像地址首次安装后,配置软件源sed -i "1iServer = http://mirrors.ustc.edu.cn/msys2/mingw/i686" /etc/pacman.d/mirrorlist.mingw32sed -i "1iServer = http://mirrors.ustc.edu.cn/msys2/mingw/x86_64" /etc/pacma...

FAT32文件_fat32返回值-程序员宅基地

文章浏览阅读1.1k次。/*---------------------------------------------- * 模 块 名:文件系统 * 功能描述:读写基于FAT32格式的数据 * 调试平台:UMP3 * * 当前版本:1.0 * 作 者:xx * 完成日期:2010-6-28 * 存在BUG:未知 * 调试结果:完成调试 * * 说 明:本文件系统_fat32返回值

Python初学者笔记(3):输出列表中的奇数/奇数项,字符串中的偶数项,字符串大小写转换...-程序员宅基地

文章浏览阅读4.5k次,点赞2次,收藏12次。【1】a=[8,13,11,6,26,19,24]1)请输出列表a中的奇数项2)请输出列表a中的奇数解:1)1 a=[8,13,11,6,26,19,24]2 print a[::2]Result:>>>[8, 11, 26, 24]2)1 a = [8,13,11,6,26,19,24]2 b = []3 for it..._用for语句筛选出自然数序列中的奇数与偶数,分别存入奇数列表ls1 与 偶数列表ls2,分两行打印输出

Python安装包下载、环境配置与工具包安装教程(详细版)_pystdf安装包-程序员宅基地

文章浏览阅读7k次,点赞11次,收藏62次。一、安装包下载网盘:链接:https://pan.baidu.com/s/1FrFj8Flcwr_ZJH91OxoF5A 提取码:2442二、环境配置1、下载完解压后双击 python-3.8.0a4-amd64.exe,注意:一定勾选Add Python 3.8 to PATH, 会自动配置环境变量 2、在cmd中输入python 验证是否安装成功三、工具包下载1、安装pip,首先进入cmd命令是:pip install pip查看是否安装成功命令: == pip show pi_pystdf安装包

随便推点

前端面试题1(html)-程序员宅基地

文章浏览阅读607次。HTML * Doctype作用?严格模式与混杂模式如何区分?它们有何意义?1.<!DOCTYPE> 声明位于文档中的最前面的位置,处于 <html> 标签之前。此标签可告知浏览器文档使用哪种 HTML 或 XHTML 规范2. 所谓的标准模式是指,浏览器按 W3C 标准解析执行代码;怪异模式则是使用浏览器自己的方式解析执行代码,因为不同浏览..._html 面试题

选项卡:选择一个按钮改变div的背景颜色_点击修改颜色按钮,输入颜色,修改div背景颜色-程序员宅基地

文章浏览阅读1.2k次。<!-- 选项卡:选择一个按钮改变div的背景颜色1. 获取三个button按钮和一个div2. 最先给div设置基本背景颜色3. 3个button设置onclick事件4. 点击按钮之后,div.style.cssText={background-color:选定颜色}--><!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8"> <meta _点击修改颜色按钮,输入颜色,修改div背景颜色

GUI是什么-程序员宅基地

文章浏览阅读7.3w次,点赞38次,收藏135次。GUI的全称为Graphical User Interface,图形化界面或图形用户接口,是指采用图形方式显示的计算机操作环境用户接口。与早期计算机使用的命令行界面相比,图形界面对于用户来说更为简便易用。GUI的广泛应用是当今计算机发展的重大成就之一,它极大地方便了非专业用户的使用人们从此不再需要死记硬背大量的命令,取而代之的是通过窗口、菜单、按键等方式来方便地进行操作。而嵌入式GUI具有下面几个方面的基本要求:轻型、占用资源少、高性能、高可靠性、便于移植、可配置等特点。_gui

gitlab安装,使用,备份,恢复-程序员宅基地

文章浏览阅读96次。gitlab安装,使用,备份,恢复git是一个版本控制器在分布式版本控制系统里,客户端并不只提取最新版本的文件快照,而是把代码仓库完整地镜像下来。这么一来,任何一处协同工作用的服务器发生故障,事后都可以用任何一个镜像出来的本地仓库恢复。因为每一次的提取操作,实际上都是一次对代码仓库的完整备份。1.gitlab介绍GitLab 是一个用于仓库管理系统的开源项目,使用Git作为代码管理工具,并..._gitlab-ce-8.9.5-ce.0.el6.x86_64.rpm

Centos7下Hortonworks的Ambari-server和Hadoop集群平台重装._ambari集群中有一台重装系统-程序员宅基地

文章浏览阅读6.3k次。Ambari是apache的顶级项目, 是一套类似一键包安装hadoop集群的快速部署工具.地址在这里: https://ambari.apache.org/Apache Ambari本文是因为配置kerberos 授权的时候, 需要加安装一些功能, 比如tez的时候, 某个包(pig 安装失败,) 导致禁用kerberos 无效. 进而陷入死循环不得不重装. 因为是物理机没有回滚机制. 所以记录_ambari集群中有一台重装系统

使用SDL2_mixer库播放MP3音乐_sdl play mp3-程序员宅基地

文章浏览阅读1.7k次。使用SDL2_mixer库播放MP3音乐运行环境:Ubuntu:16.04开发环境准备安装libsdl2-mixer-dev~$ sudo apt install libsdl2-mixer-dev需要包含的头文件#include <SDL2/SDL.h>#include <SDL2/SDL_mixer.h>需要链接的库文件set(CMAKE_CX..._sdl play mp3