Koios1143的筆記

發表於 分類於

Atcoder DP Contest pI

題敘

https://atcoder.jp/contests/dp/tasks/dp_i
有 $n$ 個硬幣，每個硬幣有翻到正面的機率 $p_i$
問正面多於反面的機率有多少

想法

嘗試遮住最後一個硬幣，觀察每次擲硬幣會影響到哪些
定義 $DP[i]$ 表示有 $i$ 個硬幣為正面的機率
則有轉移式 $DP[i] = DP[i-1]*arr[i] + DP[i]*(1-arr[i])$
且已知 $DP[0] = 1$

閱讀全文 »

發表於 更新於 分類於

Atcoder DP Contest pH

題敘

https://atcoder.jp/contests/dp/tasks/dp_h
給一張二維圖，圖上有障礙物，問從點 $(1,1)$ 走到點 $(h,w)$ 的方法數模 $10^9+7$ 為多少

想法

跟走樓梯的DP概念相同
同一個格子只能從左邊或上面轉移過來，則方法數會是兩者相加
定義 $DP[i][j]$ 表示在第 $(i,j)$ 格的方法數
則有轉移式 $DP[i][j] = DP[i-1][j] = DP[i][j-1]$
且已知 $DP[1][1] = 1$

閱讀全文 »

發表於 分類於

Atcoder DP Contest pG

題敘

https://atcoder.jp/contests/dp/tasks/dp_g
給一張有向無環圖$G$，求最長路徑大小

想法

直接DFS每個點是從哪些點轉移過來
將答案直接儲存在點上，當已經有答案時直接回傳，就跟DP的概念一樣
定義 $DP[i]$ 表示點 $i$ 為終點時的最長路徑
則有轉移式 $DP[i] = max(DP[k]+1)$，其中 $k$ 表示所有走向點 $i$ 的點

閱讀全文 »

發表於 更新於 分類於

Atcoder DP Contest pE

題敘

https://atcoder.jp/contests/dp/tasks/dp_e
與pD相同，但是重量可以來到 $10^9$
問最大價值

想法

因為重量太大了，導致無法使用pD的作法
但是價值不大，可以從這裡下手
將問題倒過來思考，如果知道在某價值下最小的重量總和，那麼只要重量總和小於等於題目要求，那麼該價值的最大值即為解

閱讀全文 »

發表於 更新於 分類於

Atcoder DP Contest pD

題敘

https://atcoder.jp/contests/dp/tasks/dp_d
有一個負重上限為 $w$ 的背包
有 $n$ 個物品，每個物品都有其重量及價值
求能放入背包內的最大價值為何

想法

對於每個物品查看用該物品能組出的重量分別能形成的價值為多少並不斷更新
定義 $DP[i][j]$ 表示在前 $i$ 物中最大負重為 $j$ 時的最大價值
則可得轉移式 $DP[i][j] = max(DP[i-1][j], DP[i-1][j-cost[i]]+value[i])$
且為了避免取同物品多次的狀況，最大負重從 $w$ 開始往下算
不過在實作上可以發現到每次取的都是 $i-1$ 的狀態，所以實際上可以壓縮成一維

閱讀全文 »