Doing Homework

? HDU - 1074?

這是一道狀態(tài)壓縮DP（從N <= 15就可以看出來）。

我們定義二進(jìn)制狀態(tài)S代表的是目前已經(jīng)安排好的任務(wù)

dp[S].val代表的是目前已經(jīng)安排好的任務(wù)的扣分的最小值

dp[S].sumT代表的是目前已經(jīng)安排好的任務(wù)所需要的時(shí)間

狀態(tài)轉(zhuǎn)移的時(shí)候我們只考慮下一個(gè)任務(wù)的選取

設(shè)S通過新任務(wù)的選取轉(zhuǎn)移到下一個(gè)狀態(tài)tar

tar = S | (1<<i) ;選取第i個(gè)任務(wù)

那么狀態(tài)轉(zhuǎn)移一可以寫成

if(dp[S].sumT + Ts[i] > ddls[i])//當(dāng)新任務(wù)的選取超過了ddl而被扣分，那么計(jì)算扣分cost = dp[S].sumT + Ts[i] - ddls[i]; if(dp[tar].val > dp[S].val + cost ){//更新dp[tar].val = dp[S].val + cost;dp[tar].sumT = dp[S].sumT + Ts[i];dp[tar].pre = S;//設(shè)置前驅(qū)，記錄路徑 }完整代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; struct node{int sumT;int val;int pre; }; node dp[(1<<15)]; const int INF = 1e9; const int MAX = 20; int ddls[MAX]; int Ts[MAX]; char names[MAX][100]; int order[16]; int calc(int x){int cnt = 0;while(x){cnt++;x >>= 1;}return cnt-1; } int main(){int T;scanf("%d",&T);while(T--){for(int i = 0;i < (1<<15);i++){dp[i].val = INF;}int n;scanf("%d",&n);for(int i = 0;i < n;i++){scanf("%s %d%d",names[i],&ddls[i],&Ts[i]);}dp[0].pre = 0;dp[0].sumT = 0;dp[0].val = 0;for(int S = 0;S < (1<<n);S++){for(int i = 0;i < n;i++){if((S & (1<<i)) == 0){int tar = S|(1<<i);int cost = 0;if(dp[S].sumT + Ts[i] > ddls[i])cost = dp[S].sumT + Ts[i] - ddls[i];if(dp[tar].val > dp[S].val + cost ){dp[tar].val = dp[S].val + cost;dp[tar].sumT = dp[S].sumT + Ts[i];dp[tar].pre = S;}}}}cout<<dp[(1<<n)-1].val<<endl;int S = (1<<n)-1;int cnt = n;while(S){int nS = dp[S].pre;int t = calc(nS ^ S);order[--cnt] = t;S = nS;}for(int i = 0;i < n;i++){cout<<names[order[i]]<<endl;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的动态规划训练16 [Doing Homework HDU - 1074 ]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。