這一周以區間dp和打訓練賽為主，也嘗試了每天寫一點博客但是只寫了一天的，
區間dp其實還有很多沒懂的，但是區間dp有一點區別線性dp簡單的地方就是他的模式相對固定，是通過對每個區間進行動態規劃，求解區間上的最優解，主要是通過合并小區間的最優解來得出整個打的區間的最優解，我們主要的代碼，首先需要列舉區間長度len來當做每個區間的長度，再根據區間長度再次列舉區間的開始點和結束點，最后再根據對每個小區間進行分割來求出小區間的最優解，進而遞推出整個區間的最優解，這是區間dp的大體思路但是在實作的時候我總是在死磕他的實作程序，和他的實作的流程，導致我一直不是很理解區間dp，就是有點暈了，也想了好幾天最終看了幾個朋友的題解有一絲絲的明白了，下面來列出幾個例題來鞏固鞏固，
（1）區間dpA：
有n個聚會求穿衣服的最少量
鏈接如下：
https://vjudge.net/contest/434302#problem
這個題當初想了還幾天，看了別人的題解之后也不明白題解是怎么出來的，后來想了一想我的不理解并不是在于這個題目，而是在于整個區間dp的實作程序，求最少穿衣數，那么我們就需要列舉可以分割的區間來更新答案，分為兩個情況，第一種情況就是開始位置和結束位置不相同，不相同的話區間陣列+1，相同的話我們首先來看這道題 求給定區間的服裝最小值，那么我們把這個區間分為兩個區間求這兩個區間的最小值然后再合并，把他分為由i到k和由k+1到j兩個區間，那么這兩個區間再去合并，這兩個區間最小值得和就是整個區間的最小值，那么這個dp方程就出來了，**dp方程為dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j])**再處理一下細節每個到每個區間是都+1就行了，當初在這個區間dp的時候就死磕在了他為啥第k件的時候穿上或者脫下要用這一個方程，
（2）能量項鏈 區間dp P題：
求項鏈串釋放的最大能量，
鏈接如下：
https://vjudge.net/contest/434302#problem/P
其實這一個題是一個環狀的題我們做這種題有一個小細節就是要把這個環展成一個鏈來解決，合成鏈之后我們就來根據一的做法來做，把這個整個區間分成兩個區間來進行合并求出狀態方程來，那么把這分成兩個的區間在合并到一起，那么狀態方程就是f[l][r]=f[l][k]+f[k][r]+w[l]*w[k]*w[r]，在注意細節就行了
其實這幾天主要是繞過區間dp的彎兒來也沒做幾個題，
再就是這幾天的訓練這幾天的訓練開始演算法比較多了，還有就是有一些思維的題目，你要是想出來了，那么代碼就很簡單，你要是想不出來，那么你用平常的方法你就很難把它給做出來，通過這一陣的訓練感覺進步還是蠻明顯的那些思維題大部分不是很難的還是能夠做出來，現在的問題就在于演算法和速度和罰時上，演算法其實我們也沒學多少，就學了貪心、博弈和dp，我們隊dp比較差沒做出幾個來，博弈的話做的那幾個題感覺都是博弈里面簡單的，那種一般的博弈我們還沒見過，速度上因為我們隊讀題的只有一個人我們另外兩個人都看不懂題目導致我們翻譯的時候會很慢，還有就是罰時，我有的時候很簡單的題目會達不到一次過（這個毛病不僅僅在一次題中了）要不就是這個變數看錯了要不就是那個變數看成了其他的，其實我們隊最大的需要克服的就是第一點，以后也會加大對演算法題的理解和解決，
4月20日
今天學了區間dp花了好幾天的時間終于把區間dp里面最簡單的那個線性的石子合并看明白了，
關于期間dp有一個套用的公式
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++） //區間長度為1的初始化
dp[i][i] = 0;
for (int len = 2; len <= n; len++) //列舉區間長度
{
for (int i = 1, j = len; j <= n; i++, j++) //區間[i,j]
{
//DP方程實作
}
}
一般的區間dp都會用到二維陣列，
我們在做區間dp的題目的時候如果多個數字我們想不到他的最優解法的話可以通過由短區間推到長區間（這好像有一個名詞叫做決策性單調）
關于今天的訓練，感覺就是針對演算法來的，所以我們做的不是很樂觀，總結出來無非兩點：
（1）我們對演算法掌握的還不是很熟悉，
（2）因為體量和英文邊長的原因我們的對題目的理解也有一點偏差，
識訓：
今天我我在做a的時候發現了sort的一種特別的用法雖然還不知道對不對：
struct ch{
int x,y;
bool flag=false;
}arr[200010];
bool cmp(ch a,ch b)
{
if((a.y-b.y)==(a.x-b.x))
{
a.flag=true;
b.flag=true;
}
}
int main()
{
sort(arr+1,arr+n+1,cmp);
}
感覺通過這樣雖然不能實作排序但是可以起到了選擇的目的，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280550.html
標籤：其他
上一篇：小白的演算法課-方法論
下一篇：DS1302時鐘芯片的使用