P2157 SDOI2009 學校食堂 狀壓DP

2022-09-22 22:15:12 字數 809 閱讀 8836

有點複雜,自行瀏覽吧 題目連結

我們發現dp轉移時需要記錄以下幾個資訊:

打飯佇列的隊首是誰,上一個打飯的是誰,佇列前\(b[i]\)個人的狀態

然後我們根據這些資訊設立dp狀態,記\(f[i][j][k]\)表示該第\(i\)個人打飯(等價於前\(i-1\)個人已經買完飯)此時佇列前7個人的狀態是\(j\),上一個打飯的人是\(i+k\)。由於打飯的人在\(i\)的前後都可以,所以\(k\)的範圍就是\([-8,8]\),加上偏移量就是\([0,16]\)

接下來我們考慮轉移,分為兩種情況:

第\(i\)個人已經買完飯了,也就是說直接將狀態轉移到\(i+1\)就可以了

f[i+1][j>>1][k-1]=min(f[i+1][j>>1][k-1],f[i][j][k]);
第\(i\)個人還沒有買飯,那就在所有人都能忍受的範圍內列舉買飯的人是誰

f[i][j|(1《狀態初始化為\(f[1][0][7]\)表示該第\(1\)個人買飯,此時身後所有人都沒有買完,上一個買的人是第\(7-8\)個,最後統計列舉\(i\)然後取\(f[n+1][0][i]\)的最小值

#includeusing namespace std;

namespace zzc}}

}}}}

int ans=0x3f3f3f;

for(int i=0;i<=8;i++) ans=min(ans,f[n+1][0][i]);

printf("%d\n",ans);

} }}

int main()

P2157 SDOI2009 學校食堂

貌似我這個做法就是用了佇列,無腦一點。 首先分析一下題目性質。如果 x 是打完飯的人當中排隊最靠後的,那麼1到x 8這些人肯定都打完飯了。定...

P2157 SDOI2009 學校食堂 狀壓DP

排隊買飯,時間為前一個人和後一個人的異或和,每個人允許其後面b i 個人先買到飯,問最少的總用時。 用dp i j k 表示1 i 1已經買好飯了,第i個人後面買飯情況為j,最後一個打飯的是i k。 include include include include include include in...

洛谷 P2157 SDOI2009 學校食堂

每個人有一個口味,食堂每次只能為一個人做菜 做每道菜所需的時間是和前一道菜有關的,若前一道菜的對應的口味是a,這一道為b,則做這道菜所需的時間為a 異或 b 每個人都有一個容忍度,最多允許緊跟他身後的bi 個人先拿到飯菜, 求食堂完成所有菜所需的最少時間 使用狀態壓縮。f i j k 表示當前處理第...