0%

資芽第七週:動態規劃(一)

上課內容

  • 使用DP時機:

    • 最優解問題
    • 計數問題
    • 重複子問題
  • DP 使用過程

    • 定義狀態
    • 狀態轉移
    • 找到一個會AC的作法,再慢慢優化
  • 使用注意事項:

    • 寫好時間複雜度
    • 用「拉」的
    • 用「推」的
    • 盡量使用由下而上
  • DP例題

    • 跑步問題(zj b589)
    • 最大連續和
    • 最大不連續和(npsc 2017)
    • Chest of Drawers (UVA 11420)
    • 最大和矩陣問題
    • 矩陣最大方形
    • 矩陣乘法問題
    • 消消樂(UVA 10559 Blocks)

上機作業

円円數磁磚

題目連結
我不會寫轉移式子啊…
首先可以觀察到,因為兩個磁磚的排法有3種,首先可以列出$f(n) = 3\times f(n-2)$ 這個式子,但觀察之後可以發現,如果排列的磁磚不能被兩兩分割,也可是一種新的排法。而對於固定的尺寸大小只會有一種排法,但因為可以顛倒放,因此視為兩種組合。
轉移式:
$f(n) = 3\times f(n-2)+2\times(f(n-4)+f(n-6)…)$
經過數學帶入消去:
$f(n-2) = 3\times f(n-4)+2\times(f(n-6)+f(n-8)…)$
$f(n) = 4\times f(n-2)-f(n-4)$

邊界:$dp[0] = 1, dp[2] = 3$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
int t;

signed main(){
cin>>t;
int dp[100005];
memset(dp, 0, sizeof(dp));
dp[0] = 1;dp[2] = 3;dp[3] = 0;
for(int i=4;i<=100001;i+=2)dp[i] =(4*dp[i-2]-dp[i-4]+1000007)%1000007;
while(t--){
int n;cin>>n;
cout<<dp[n]<<endl;
}
}

円円送禮物

題目連結
以後寫DP幾種組合問題就是像這一題一樣暴力破解
把每一種情況都寫清楚,不惜開三維陣列也沒關係
總之,$dp[i][k][j]$ 代表長度為i,左邊為顏色k,右邊為顏色j
(紅色:0、綠色:1、藍色:2)
列出每一種狀態的轉移式就好
不過,即使頭尾是一藍一綠,但也必須轉移,因為一藍一綠可以在頭或尾加上其他顏色,組成合法解,不過不要輸出就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define int long long
#define ios ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
int t;

signed main(){
ios;
int dp[100005][3][3];//0:red,1:green,2:blue
dp[1][0][0] = 1;dp[1][1][1] = 1;dp[1][2][2] = 1;
dp[2][0][0] = dp[2][0][1] = dp[2][0][2] = 1;
dp[2][1][0] = dp[2][1][1] = dp[2][2][0] = dp[2][2][2] = 1;
dp[2][1][2] = dp[2][2][1] = 0;

for(int i=3;i<100005;i++){
dp[i][0][0] = (dp[i-1][0][0]+dp[i-1][0][1]+dp[i-1][0][2])%1000007;
dp[i][0][1] = (dp[i-1][0][0]+dp[i-1][0][1])%1000007;
dp[i][0][2] = (dp[i-1][0][0]+dp[i-1][0][2])%1000007;

dp[i][1][0] = (dp[i-1][1][0]+dp[i-1][1][1]+dp[i-1][1][2])%1000007;
dp[i][1][1] = (dp[i-1][1][0]+dp[i-1][1][1])%1000007;
dp[i][1][2] = (dp[i-1][1][0]+dp[i-1][1][2])%1000007;

dp[i][2][0] = (dp[i-1][2][0]+dp[i-1][2][1]+dp[i-1][2][2])%1000007;
dp[i][2][1] = (dp[i-1][2][0]+dp[i-1][2][1])%1000007;
dp[i][2][2] = (dp[i-1][2][0]+dp[i-1][2][2])%1000007;

}
int n;cin>>n;
while(n--){
int a;cin>>a;
cout<<(dp[a][0][0]+dp[a][0][1]+dp[a][0][2]+dp[a][1][0]+dp[a][1][1]+dp[a][2][0]+dp[a][2][2])%1000007<<endl;
}
}

取數字1

題目連結
定義:$dp[i]$ 為取第i個數字的的最大值
轉移式:$dp[i] = max(dp[i-2]+dp[i-2])+arr[i]$
可以發現到,因為$arr[i]$ 都是正數,因此加越多數字就代表最後的數值越大,而相鄰的兩項不能轉移,因此就要看$dp[i-2],dp[i-2]$其中i-4不用看是因為已經包含在i-2裡面了
邊界:$dp[1] = arr[1],dp[2] = arr[2],dp[3] = arr[1]+arr[3]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int t;

int main(){
cin>>t;
while(t--){
int n,arr[100005];cin>>n;
int dp[10005];
memset(dp,0,sizeof(dp));
memset(arr,0,sizeof(arr));

for(int i=1;i<=n;i++)cin>>arr[i];
dp[1] = arr[1];dp[2] = arr[2];dp[3] = arr[1]+arr[3];
for(int i=4;i<=n+1;i++){
dp[i] = max(dp[i-2],dp[i-3])+arr[i];
}
cout<<max(dp[n],dp[n-1])<<endl;
}
}

取數字2

題目連結
上面取數字1的進階版,可以一樣定義,不過轉移式要稍微改變(其實就只是把原本只有2的區間擴大成k)
定義:$dp[i]$ 為取第i個數字的的最大值
轉移式:
$dp[i]=max(arr[j]+arr[i]),2k\leq i \leq n,i-2k\leq j \leq i-k$
轉移式比較複雜一點,不過就是取數字1的延伸
邊界:
$dp[i] = arr[i],1\leq i \leq k$
$dp[i]=max(arr[j]+arr[i]),k+1\leq i \leq 2k,1\leq j \leq i-k$

邊界的話,如果要說成是轉移式也是可以啦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
using namespace std;
int t;

signed main(){
ios;
cin>>t;
while(t--){
int n,arr[100005],k;cin>>n>>k;
int dp[100005];
memset(dp,0,sizeof(dp));
memset(arr,0,sizeof(arr));

for(int i=1;i<=n;i++)cin>>arr[i];
//[1,k]的邊界轉移
for(int i=1;i<=k;i++)dp[i] = arr[i];
//[k+1,2k]的邊界轉移
for(int i=k+1;i<=2*k;i++){
for(int j=1;j<=i-k;j++){//看可以配上[1,k]最大的那一個
dp[i]=max(dp[i],arr[j]+arr[i]);
}
}
for(int i=2*k+1;i<=n;i++){
for(int j = i-2*k;j<=i-k;j++){//開始轉移,掃描k次
dp[i] = max(dp[i],dp[j]+arr[i]);
}
}
cout<<max_element(dp, dp+n+1)<<endl;
}
}

合成円円

題目連結
開始接觸到區間DP,比單純的DP又多了一些要注意的地方
上網查關於區間DP的資料,一般都會有這些內容:

1
2
3
4
for (枚舉區間長度)
for (枚舉左端點)
for (枚舉分割點)
f[l, r] = f[l, k] + f[k, r] + val(l, r)

主要就是,從小的區間長度開始(大的區間需要小的區間的答案),枚舉左端點可以知道區間的範圍,接著再依序枚舉在區間內分割點,把長度為n的區間長度跑完之後就完成了
有了這一個$O(n^3)$ 的演算法,就可以開始來實作

定義:
$dp[i][j]$ $(1 \leq i,j \leq n)$ 為合併區間 $[i,j]$ 所需要的花費
轉移式:
$dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum_{i,j}),i \leq k \leq j$
合併區間$dp[i][k],dp[k+1][j]$的花費為兩者相加再加上區間[i,j]的總和(可以用前綴維護)
邊界:
$dp[i][i] = 0,1 \leq i \leq n$

這個演算法的複雜度是$O(n^3)$,之後可以用dp優化的技巧做到更快

問題:這題可不可以用Greedy?
我們如果每一次都找兩兩相鄰相加總和最小的兩個加起來,做n-1次,是不是可以找到最佳解?(如果可以,那幹嘛還要辛苦維護$n^3$的算法XD)

Q:答案是不行,那要反例何時出現?

10 7 6 7

這一組測資如果用Greedy做是63,用dp做是60,可以發現到,如果數字兩兩相加相等,那先加後加的順序就很重要,有可能因為順序不對(先加中間的7跟6),導致7沒辦法跟10合併產生更加的解法!

找反例的方法: 這一筆測資是利用隨機生成大量的數字去找出有沒有不一樣,方法by:

這一題就先這樣,不過區間DP感覺就是可以很難的東西
時間複雜度$O(n^3)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0);
#define int long long
using namespace std;
int t;

signed main(){
ios;
cin>>t;
while(t--){
int n,arr[105],pre[105];cin>>n;
int dp[105][105];
memset(pre, 0, sizeof(pre));
memset(dp, 0x3f3f3f3f, sizeof(dp));
for(int i=1;i<=n;i++){
cin>>arr[i];
pre[i] = pre[i-1]+arr[i];
dp[i][i] = 0;
}

for(int len = 2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){//區間[i,j]長度為len,則j = i+len-1
int j = i+len-1;
for(int k=i;k<=j;k++){
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+pre[j]-pre[i-1]);
}
}
}
cout<<dp[1][n]<<endl;
}
}

手寫作業

這一週沒有手寫!因為下禮拜是第一階段認證考