• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Climber.pI的OI之路

            Through the darkest dark,may we see the light.

            Dp札記

            記錄寫過的dp題目,并分類,嘗試總結出某類題目的一般模型.

            (題目前打*的未編程驗證)

            【線性模型】

            Tyvj 1049 最長不下降子序列問題 [O(n^2) [還存在基于二分查找的O(nlogn)算法]]

            • [狀態] f[i]表示從1到i的最長不下降子序列. 最大值需更新.
            • [方程] if(a[j]<=a[i]) f[i] = max{f[j]} (0<j<i, 1<i<=n)

            NOIp 2004 合唱隊形 [O(n^2), 雙向最長上升子序列]

            • [方程] f[i] = max{f[j]}+1 , 枚舉k(0<=k<=n).

            Rqnoj 164 最長公共子串 [記錄方案 子串連續 O(n^2)]

            • [狀態] f[i][j]表示 子串A第i個字符 和 子串B第j個字符 前 公共子序列長度
            • [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j],a[i-1]=b[j-1])|max{f[i-1][j],f[i][j-1]}

            UVa 111/10405  [最長公共子序列問題,O(n^2). 可以使用滾動數組降至O(n).]

            • [狀態] f[i][j]表示 子串A第i個字符 和 子串B第j個字符 前 公共子序列長度
            • [方程] f[i][j] = f[i-1][j-1]+1(a[i]=b[j])|max{f[i-1][j],f[i][j-1]}

            UVa 507 [最大連續和,O(n).]

            • [狀態] f[i]表示當前子序列和(非負)
            • [方程] f[i]=max{f[i-1]+a[i], a[i]},遞推過程中需更新最大值.

            【矩陣模型】

            *UVa 10285 滑雪 [記憶化搜索,最長下降子序列二維版本]

            • [狀態] f[i][j]表示從(i,j)開始的最長下降子序列長度.
            • [方程] f[i][j] = max{f[i-1][j], f[i][j-1], f[i+1][j], f[i][j+1]}+1(f[i][j]>f[i-1][j]..)

            UVa 108

            • 最大矩陣和,O(n^3),方程不會. 最大連續和的二維版本.

            NOIp 2000 方格取數 O(n^4)

            • [狀態] f[i][j][k][l]表示兩人分別到(i,j)、(k,l)所取過的數的和.G[i][j]表示方格里的數.
            • [方程] f[i][j][k][l] = max{f[i-1][j][k-1][l], f[i-1][j][k][l-1], f[i][j-1][k-1][l], f[i][j-1][k][l-1]}+G[i][j]+(i==k&&j==l ? 0 : G[k][l])

            NOIp 2008 傳紙條

            (1) O(n^4)

            • [狀態] f[x1][y1][x2][y2] 表示從出發點分別到(x1,y1)、(x2,y2)取的最大值.G[x][y]表示該格的數.
            • [方程] f[x1][y1][x2][y2] = max{f[x1-1][y1][x2-1][y2],f[x1-1][y1][x2][y2-1],f[x1][y1-1][x2-1][y2],f[x1][y1-1][x2][y2-1]}+G[x1][y1]+G[x2][y2](如果位置不重復)
            • [一個重要優化] 顯然有y2=x1+y1-x2(y2>0),因而時間復雜度可以降到O(n^3).Cena顯示總用時從近4s降到近0.3s,效果明顯.

            *(2) O(n^3)

            • [狀態] f[p][x1][x2],p表示經過的格子數.
            • [方程] f[p][x1][x2]=max{f[p-1][x1-1][x2-1],f[p-1][x1-1][x2],f[p-1][x1][x2-1],f[p-1][x1][x2]}+G[x1][p-x1]+G[x2][p-x2](如果位置不重復)

            USACO 5.3.4/3.3.4 [矩陣dp,O(n^2)]

            • [狀態] f[i][j]表示以(i,j)為右下角的正方形最大邊長
            • [方程] f[i][j] = min{f[i-1][j], f[i-1][j-1], f[i][j-1]}+1 (0<=i,j<n)
            • [預處理] 若G[i][j]=1則f[i][j]=1.

            【背包問題】

            USACO 3.3.2

            • [狀態] f[a1][a2][a3][a4][a5]為買a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5時,所需的最少價格
            • [方程] f[a1][a2][a3][a4][a5] = min{f[a1-p[i][1][a2-p[i][2][a3-p[i][3][a4-p[i][4]][a5-p[i][5]+p[i][0]} (0<i<=s, ak-p[i][k]>=0,p[i][0]是優惠后的價格)
            • [邊界條件] f[0][0][0][0][0]=0;
            • USACO官方解法很有啟發性,用最短路,把每種狀態[a1][a2][a3][a4][a5](a1件物品1,a2件物品2,a3件物品3,a4件物品4,a5件物品5)看成一個點,則至多7776個點,而每個優惠就是一條邊,則至多105條邊。 接下來就是求[0,0,0,0,0]到目標狀態的最短路,用Dijkstra(Heap優化)即可.

            USACO 3.1.2 [完全背包問題, O(n)或O(n^2).]

            • [狀態] f[i][j]表示放入第i個物體后剩余體積為j
            • [方程] f[i][j] = f[i-1][j] + f[i][j-c[i]]+w[i]

            USACO 3.1.6 [完全背包問題,O(n).]

            • [狀態] f[i]表示湊成i分郵資的最少郵票數.
            • [方程] f[i] = min{f[i-v[j]]+1} (i-v[j] >= 0, 0<=i<n, f[0] = 0).

            USACO 2.3.4

            • [狀態] f[i,j]表示前i種貨幣構成j的方法數,用c[i]記錄貨幣的面值.
            • [方程] f[i,j]=f[i-1,j]; 不用第i種貨幣
                           f[i,j]=f[i-1,j]+f[i,j-c[i]] 用第i種貨幣,j>=c[i]

            【樹形】

            USACO 2.3.2

            • [狀態] f[i,j]表示用i個點組成深度最多為j的二叉樹的方法數,則:
            • [方程] f[i,j]=∑(f[k,j-1]×f[i-1-k,j-1])(k∈{1..i-2}) 
            • [邊界] f[1,i]=1
            • 我們要求的是深度恰好為K的方法數S,易知S=f[n,k]-f[n,k-1]。但需要注意的是,如果每次都取模,最后可能會有f[n,k]<f[n,k-1],所以可以用S=(f[n,k]-f[n,k-1]+v) mod v

             

            【其他類型】

            USACO 1.5.1 [數字三角形]

            • [狀態] f[i][j]表示從(i,j)開始經過的數字的最大和
            • [方程] f[i][j] = max{f[i+1][j], f[i+1][j+1]}+a[i][j]

            USACO 3.3.5 [博弈問題]

            • [狀態] s[i][j]表示從i加到j的和, 枚舉l=j-i. f[i][j]表示從i到j先取者能得到的最大數字和.
            • [方程] f[i][j] = s[i][j] - min{f[i+1][j], f[i][j-1]}

            USACO 3.2.2

            • [狀態] f[n][m]表示至多m個1的n位二進制數數量
            • [方程] f[n][m] = f[n-1][m] + f[n-1][m-1] (f[0][m] = 1)

            posted on 2010-10-03 12:23 Climber.pI 閱讀(467) 評論(1)  編輯 收藏 引用 所屬分類: 動態規劃

            Feedback

            # re: Dp札記[未登錄] 2011-05-18 19:14 Climber.pI

            我發現我只有上面類型的dp我會做...看而不寫基本全忘  回復  更多評論   

            热99re久久国超精品首页| 国产A级毛片久久久精品毛片| 国产精品久久久久影院色| 国产精品久久永久免费| 久久综合狠狠综合久久97色| 亚洲午夜久久久| 久久这里只有精品18| 国产精久久一区二区三区| 久久伊人精品一区二区三区| 少妇精品久久久一区二区三区| 久久亚洲国产中v天仙www| 久久婷婷五月综合色奶水99啪| 久久综合给合久久狠狠狠97色 | 久久亚洲精品成人AV| 97久久精品人人澡人人爽| yy6080久久| 久久精品国产只有精品66 | 久久精品卫校国产小美女| 国产精品gz久久久| 久久综合久久自在自线精品自 | 大美女久久久久久j久久| 久久人人爽人人爽人人AV| 波多野结衣久久精品| 久久综合视频网站| 国产精品青草久久久久福利99| 久久国产精品成人影院| 亚洲欧美日韩精品久久亚洲区| 国产欧美一区二区久久| 久久夜色精品国产噜噜麻豆| 久久人人爽人人爽人人片AV不 | 国产精品久久久久AV福利动漫| 无码国产69精品久久久久网站| 久久无码AV中文出轨人妻| 亚洲欧美国产精品专区久久| 久久久久久极精品久久久| 久久久久久久久久免免费精品 | 久久WWW免费人成一看片| 2021国产精品久久精品| 天堂无码久久综合东京热| 久久久久久青草大香综合精品| 久久成人精品|