T1 JZOJ5535. 登機(board)
比賽時
一在題目串列里看到題目標題，就熱血沸騰了，不知道為什么，老師居然放了一道之前做過的題目，我清楚地記得這題是DP，于是很快碼了出來，講一講我的思路，讓你劃磁區域使乘客的登機難度總和最少，很容易可以看出是DP，我們就試著表示出階段和狀態，我們設\(f_{i,j}\)表示當前在第\(i\)到第\(i+1\)行劃磁區域，劃分了\(j\)次的最小登機難度，那么我們就考慮一下轉移，設\(k\)表示上一次劃磁區域的地方，那么從第\(k+1\)～\(i\)行是我們新劃分出來的區域，那么他對答案的貢獻在第\(i+1\)～\(s\)行，我們斷開以后就不再影響后面的所有行，于是，就要想一個方法，可以快速求出某幾個連續的行對后面幾個連續的行的貢獻，我們設\(a_{i,j}\)表示第\(i\)行對第\(j\)行的貢獻，我們可以對這個陣列進行二維前綴和，這個相信大家都會，得到一個陣列\(sum_{i,j}\)就可以輕松的求出貢獻了，設當前劃磁區域的位置為\(i\)，已經劃分了\(j\)次，上一次劃分的位置為\(k\)，狀態轉移方程為\(f_{i,j}=min(f_{k,j-1}-(sum_{i,s}-sum_{i,i}-sum_{k,s}+sum_{k,i}),f_{i,j})\)，初值：\(f_{0,0}=sum_{s,s}\)
之后
我的思想稍微想復雜的一點，不過也差不多
T2 JZOJ5536. 游戲
題目大意
給出一個\(W×H\)的矩陣，要你用\(w×h\)的小紙片去覆寫它，小紙片的邊與大矩陣平行，且長寬對應（不能旋轉\(90°\)），使大矩 陣不能再被一張小紙片覆寫，求最小需要多少張小紙片，
比賽時
這題我也做過，這是一道很簡單的結論題，這里我們設\(n=h\),\(m=w\)，避免誤解，我們很容易想到，一張\(n*m\)的小紙片，他能覆寫的面積是\(2n*2m\)，那么很容易推出來一個公式：\(ans=((W/m+1)/2)*((H/n+1)/2)\)，為什么要\(+1\)呢，主要是避免特殊情況的余數影響答案（同學們可以在草稿紙上畫一畫），那要是整除了呢，那也不會影響答案，
之后
同學們的另一個公式：\(ans=(\lfloor \frac{W-m}{2w} \rfloor+1)*(\lfloor \frac{H-n}{2h} \rfloor+1)\)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93586.html
標籤：其他
上一篇：2020.02.01【NOIP提高組】模擬B 組總結反思——數列（sequence） 樹 【2012東莞市選】時間流逝 挖掘機技術哪家強
下一篇：紀中集訓2020.02.05【NOIP提高組】模擬B 組總結反思——【佛山市選2010】組合數計算，生成字串 PPMM