狀壓DP

1/2ページ

8.5資訊學夏令營練習(狀壓dp)

狀壓dp的核心,就是把所有的行(不一定)轉化成二進位制。 其實這跟拼拼圖很像。 所以,我們一定要熟悉位操作,今天就是因為不熟悉位運算,浪費了很多時間。 類     型 運算子 含義 位邏輯 運算子 & 按位與 | 按位或 ^ 按位異或 ~ 取反 移位運 算   符 <<  左移 […]

2017年8月15日提高組T2 購買

Description BPM想要購買m種物品,每種物品只用購買一件。現在一共有n家商店,但走到第i家商店的路費為d[i],而在第i家商店購買第j種物品的花費為c[i,j]。問你最少需要花費多少錢。 Input 第一行包含兩個正整數n,m,表示商店數和物品數。 接下來n行,每行先是一個正整數d[i] […]

2017年8月18日提高組T2 隊伍統計

Description 現在有n個人要排成一列,編號為1->n 。但由於一些不明原因的關係,人與人之間可能存在一些矛盾關係,具體有m條矛盾關係(u,v),表示編號為u的人想要排在編號為v的人前面。要使得隊伍和諧,最多不能違背k條矛盾關係(即不能有超過k條矛盾關係(u,v),滿足最後v排在了u前 […]

邦德_紀中1236_最大權匹配_狀壓dp

Description 每個人都知道詹姆斯邦德,著名的007,但很少有人知道很多工都不是他親自完成的,而是由他的堂弟們吉米邦德完成(他有很多堂弟),詹姆斯已經厭倦了把一個個任務分配給一個個吉米,他向你求助。 每個月,詹姆斯都會收到一些任務,根據他以前執行任務的經驗,他計算出了每個吉米完成每個任務的成 […]

2017年8月16日提高組T2 疾病

Description 現在有n個人,m種病,每個人都患有若干種病。若從這些人中選出若干個人來,但選出來的人的患病集合中不超過k種病,問最多能選出多少個人。 Input 第一行三個整數n,m,k。 接下來n行,每行第一個整數s,表示第i個人患了s種病,接下來s個整數,表示第i個人患的病。 Outpu […]

bzoj3758 數數

Description 神犇最近閒來無事,於是就思考哲學,研究數字之美。在神犇看來,如果一個數的各位能夠被分成兩個集合,而且這兩個集合裡的數的和相等,那麼這個數就是優美的(具體原因就只有神犇才知道了)。現在神犇在思考另一個問題,在區間[a,b]中有多少個數是優美的?這個問題對於神犇來說很簡單,相信對 […]

bzoj1806 [Ioi2007]Miners 礦工配餐

Description 現有兩個煤礦,每個煤礦都僱用一組礦工。採煤工作很辛苦,所以礦工們需要良好飲食。每當一輛食品車到達煤礦時,礦工們便會產出一定數量的煤。有三種型別的食品車:肉車,魚車和麵包車。 礦工們喜歡變化的食譜。如果提供的食品能夠不斷變化,他們的產煤量將會增加。每當一個新的食品車到達煤礦時, […]

bzoj3195 [Jxoi2012]奇怪的道路 狀壓dp

Description 小宇從歷史書上瞭解到一個古老的文明。這個文明在各個方面高度發達,交通方面也不例外。考古學家已經知道,這個文明在全盛時期有n座城市,編號為1..n。m條道路連線在這些城市之間,每條道路將兩個城市連線起來,使得兩地的居民可以方便地來往。一對城市之間可能存在多條道路。 據史料記載, […]

bzoj1076 [SCOI2008]獎勵關

Description 你正在玩你最喜歡的電子遊戲,並且剛剛進入一個獎勵關。在這個獎勵關裡,系統將依次隨機丟擲k次寶物, 每次你都可以選擇吃或者不吃(必須在丟擲下一個寶物之前做出選擇,且現在決定不吃的寶物以後也不能再吃)。  寶物一共有n種,系統每次丟擲這n種寶物的概率都相同且相互獨立。也 […]