題意：
? ? ? 給你一些作業，每個作業有自己的結束時間和花費時間，如果超過結束時間完成，一天扣一分，問你把n個作業完成最少的扣分，要求輸出方案。


思路：
? ? ? 狀態壓縮dp，記錄方案數的地方我用的是類似并查集的方法，記錄當前狀態是那個狀態轉移過來的，<輸出的時候可以 異或 出來>，對于字典序最小，這個比較好處理，給的是升序的，所以直接更新的時候記錄就行了，<如果沒給可以sort下>，我是開了一個dp[i]表示i狀態時的最小扣分，然后在開一個數組time[i]，記錄dp[i]是對應的當前時間，然后每一個狀態都用n個作業更新下，的到最優就行了，下面給出關鍵代碼和ac代碼


for(j = 0 ;j <= (1 << n) - 1 ;j ++)
for(i = 1 ;i <= n ;i ++)
{
? ?int tt = time[j] + node[i].cost - node[i].end;
? ?if(tt < 0) tt = 0;
? ?if(dp[j|(1<<(i-1)))] > dp[j] + tt)
? ?{
? ? ? ?mer[j|(1<<(i-1))] = j;//記錄路徑
? ? ? ? dp[j|(1<<(i-1))] = dp[j] + tt;
? ? ? time[j|(1<<(i-1))] = time[j] + node[i].cost;
? ?}
}


答案等于 dp[(1<<1)-1]?
然后是輸出路徑 ? ?

int x = (1 << n) - 1;
int id = 0;
while(x != mer[x])
{
? ?Ans[++id] = x ^ mer[x];
? ?x = mer[x];
}

for(i = n ;i >= 1 ;i --)

printf("%s\n" ,node[log2(Ans[i])+1].str); ??

#include<stdio.h> #include<string.h> #include<math.h> typedef struct {int end ,cost;char str[110]; }NODE;NODE node[20]; int dp[1<<16]; int Time[1<<16]; int mer[1<<16]; int Ans[20];int minn(int x ,int y) {return x < y ? x : y; }int maxx(int x ,int y) {return x > y ? x : y; } int main () {int t ,n ,i ,j;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++)scanf("%s %d %d" ,node[i].str ,&node[i].end ,&node[i].cost);for(i = 0 ;i <= 1 << n ;i ++)dp[i] = 1000000000 ,Time[i] = 0 ,mer[i] = i;dp[0] = 0;for(j = 0 ;j <= (1 << n)-1 ;j ++)for(i = 1 ;i <= n ;i ++){ int tt = Time[j] + node[i].cost - node[i].end;if(tt < 0) tt = 0; if(dp[j|(1<<(i-1))] > dp[j] + tt){mer[j|(1<<(i-1))] = j;dp[j|(1<<(i-1))] = dp[j] + tt;Time[j|(1<<(i-1))] = Time[j] + node[i].cost;} }printf("%d\n" ,dp[(1<<n)-1]);int x = (1<<n) - 1;int id = 0;while(x != mer[x]){Ans[++id] = x ^ mer[x];x = mer[x];}for(i = n ;i >= 1 ;i --)printf("%s\n" ,node[int(log2(Ans[i]))+1].str); }return 0; } ??

? ? ?

總結

以上是生活随笔為你收集整理的hdu1074 状态压缩dp+记录方案的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。