• HDU1074 Doing Homework(状压dp)


    题意:给定有n门课的作业,每门课交作业有截止时间,和完成作业所花费的时间,如果超过规定时间完成,每超过一天就会扣1分,求一个做作业顺序要求扣的分数最少。


    思路:因为数据最大是15,可以使用二进制来表示所有完成的状况,比如二进制位1001,代表第1和第4科目的作业完成,第2第3没有完成,那么从0到(1<

     

    AC代码:

     1 #include
     2 #include
     3 #include
     4 #include<cmath>
     5 #include<cstring>
     6 #include
     7 #include<cstdio>
     8 #include
     9 #include
    10 #define inf 0x3f3f3f3f
    11 using namespace std;
    12 typedef long long ll;
    13 const int maxn = (1<<15)+5;
    14 struct node{
    15     string name;
    16     int end;
    17     int cost;
    18 }g[35];
    19 struct node1{
    20     int time;
    21     int val;
    22     int last;
    23     int cur;
    24 }dp[maxn];
    25 int m,n; 
    26 int main(){
    27     int t;
    28     cin>>t;
    29     while(t--){
    30         int n;
    31         scanf("%d",&n);
    32         memset(dp,0,sizeof(dp));
    33         for(int i = 1;i<=n;i++) {
    34             cin>>g[i].name ;
    35             cin>>g[i].end>>g[i].cost; 
    36         }
    37         int up = 1< 38         for(int i = 1;i 39             dp[i].val = 1<<30;//设置花费的最大值 
    40             for(int j = n;j>=1;j--){
    41                 int temp = 1<<(j-1);//枚举第j门课是否完成 
    42                 if(i & temp){//如果完成 
    43                     int last = i - temp;//last为完成第j门课作业之前的状态 
    44                     int s = dp[last].time + g[j].cost - g[j].end ;//完成第j门课所需要的花费 
    45                     if(s<0) s = 0;
    46                     if(dp[last].val + s 47                         dp[i].cur = j; //i状态最后完成的科目是j 
    48                         dp[i].val = dp[last].val + s;//更新到i状态扣的分数 
    49                         dp[i].time = dp[last].time + g[j].cost;//i更新到i状态的最小时间 
    50                         dp[i].last = last; //i状态的上一个状态进行更新 
    51                     } 
    52                 }
    53             }
    54         }
    55         stack s;
    56         int temp = up - 1;
    57         printf("%d
    ",dp[temp].val);//up-1为完成的状态 
    58         while(temp){
    59             s.push(dp[temp].cur);//把路径依次读入栈中 
    60             temp = dp[temp].last;
    61         }
    62         while(!s.empty()){
    63             cout< 64             s.pop();
    65         } 
    66     }
    67     return 0;
    68 }

  • 相关阅读:
    遍历二叉树 先序+后序+中序递归 用递归序来了解递归基本样子
    若依前端部署后地址栏刷新后 出现 拦截提示
    技术公司职位
    React.FC介绍
    瑞吉外卖Linux
    PCF8591学习笔记
    安装 Android Studio 2024.1.1.6(Koala SDK35)和过程问题解决
    excel有条件提取单元格特定文本(筛选纯文字的单元格或含有数字的单元格、单元格提取不同的文本长度)
    【数据结构】——链表面试题详解
    【加载数据--自定义自己的Dataset类】
  • 原文地址:https://blog.csdn.net/s13166803785/article/details/128214949