HDU 1074 Doing Homework（状态DP）

本文主要是介绍HDU 1074 Doing Homework（状态DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

这个是一道比较简单的状态DP，数据量15，所以基本上不用怀疑这是一个状态DP问题了

对于这个题目其实还是能体现状态DP的不少精髓的

首先是位运算，判断当前状态可以由那些状态转移得到，运用与运算在遍历的时候判断

还有的就是路径记录

这片代码： i=(i & (~(1<<dp[i].val)));

当前状态是由dp[i].val转换过来的，那么这个状态由什么作业转换过来就用上面的代码就搞定了，也就是把val那一位1变成0的值

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 999999999
struct point
{char name[101];int deadline;int spend;
}po[20];
struct node
{int val;int last;int time;
}dp[1<<15+10];
int n;
int ans[20];
int main()
{int t,i,j,k,p;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0;i<n;i++)scanf("%s%d%d",po[i].name,&po[i].deadline,&po[i].spend);for(i=0;i<(1<<n);i++)dp[i].time=maxn,dp[i].val=-1,dp[i].last=0;dp[0].time=0;for(i=0;i<(1<<n);i++)for(j=0;j<n;j++){if ((i & (1<<j)))continue;p=(i | (1<<j)); if (dp[p].time>dp[i].time+max(dp[p].last-po[j].deadline,0)){dp[p].last=dp[i].last+po[j].spend;dp[p].time=dp[i].time+max(dp[p].last-po[j].deadline,0);dp[p].val=j;}}printf("%d\n",dp[(1<<n)-1].time);i=(1<<n)-1;k=0;while(dp[i].val!=-1){ans[k++]=dp[i].val;i=(i & (~(1<<dp[i].val)));}for(k--;k>=0;k--)printf("%s\n",po[ans[k]].name);}return 0;
}

这篇关于HDU 1074 Doing Homework（状态DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---