從一道簡單的dp題中學到的

2022-11-24 16:57:48 字數 3583 閱讀 9258

今天想學點動態規劃的知識,於是就看了杭電的課件,數塔問題啊,lcs啊都是比較經典的動規了,然後隨便看了看就開始做課後練習題。。。

hdoj 1421 搬寢室

題目大意:從n(n <= 2000)個數中選出k對數(即2*k個),使它們的差的平方和最小。

例如:從8,1,10,9,9中選出2對數,要使差的平方和最小,則應該選8和9、9和10,這樣最小,結果為2

因為知道是dp的題,先建個dp陣列,然後我就一直在想從 n 個數中選出 k 對,和從 n-1 個數中選出 k 對有什麼關係...

妹夫的,想了半天沒想出來有關係,一搜題解,看呆了,排序兩個大字赫然映入我的眼簾...哎呀,笨死了,我這麼多年飯算是白吃了...

只要先把這n個數排好序,那麼新加入的數如果要使用,只能是跟倒數第二個數(第n-1個)作差(未排序之前不能保證這一點,所以無法選擇)

1、如果沒用上第n個數,那麼dp[n][k] = dp[n-1][k]; 

2、如果用上了第n個數,那麼dp[n][k] = dp[n-2][k-1] + (a[n] - a[n-1])^2

只要取二者的min()就ok了,得到狀態轉移方程是:dp[i][j] = min(dp[i-1][j], dp[i-2][j-1] + (a[i] - a[i-1]) * (a[i] - a[i-1]));

程式設計如下:

1 #include2 #include3 #include4 #include5

#define inf 0x3f3f3f3f

6#define maxn 2005

7using

namespace

std;

8int

a[maxn];

9int

dp[maxn][maxn];

10int

main()

1119 memset(dp, 0x3f, sizeof

(dp));

20for (int i = 0; i < n + 1; ++i)

2124

25 sort(a + 1, a + n + 1

);26

for (int i = 2; i <= n; ++i)

2732

}33 printf("

%d\n

", dp[n][k]);34}

35return0;

36 }

插個小插曲: 關於int最大值的定義,此處是寫了 #define inf 0x3f3f3f3f....

我們知道32-int的最大值其實是0x7fffffff; 在這個程式中定義成這個值也沒有問題,下面談一下它們兩個的用處區別:

1、如果定義的最大值只是單純的用於比較,比如初始化一個min時,這樣的情景把inf設為0x7fffffff;

2、很多時候我們定義一個最大值,並不是單純的比較,而且還有鬆散的操作,比如這樣:

在很多最短路徑演算法中都有這段**

if (d[u]+w[u][v]也就是說對於一個無窮大,應該加上一個常數還是無窮大,而0x7fffffff + 1 就溢位了,顯然不符合這一基本要求。

於是,我們發現了0x3f3f3f3f(不知道哪位大神最先使用這個數的),它的值是1061109567,也就是10^9級別的,和0x7fffffff一個數量級,它加上一個常數仍然還在32int的範圍內...更加地,一個無窮大還應該滿足,正無窮大 + 正無窮大 還是無窮大,恰好地,0x3f3f3f3f + 0x3f3f3f3f = 2122219134,這個數非常大但卻沒有超過32-bit int的表示範圍,所以0x3f3f3f3f還滿足了我們“無窮大加無窮大還是無窮大”的需求。

最精妙的是,我們知道在使用memset()函式給陣列賦初值的時候,一般使用0,-1,true,false這四個引數,其他的可能會出現達不到想要結果的情形(比如全賦1,可能就不是1),因為memset是按位元組操作的,它能夠對陣列清零是因為0的每個位元組都是0,現在好了,如果我們將無窮大設為0x3f3f3f3f,那麼奇蹟就發生了,0x3f3f3f3f的每個位元組都是0x3f!所以要把一段記憶體全部置為無窮大,我們只需要memset(a,0x3f,sizeof(a))。

綜上,0x3f3f3f3f真的是在賦最大值時一個很不錯的選擇。

好的,說回到這個程式上,按照上面寫的**,提交之後,雖然能夠ac,但是執行時間是800+ms,空間是15000+k,這顯然不是我們想看到的結果...

那麼就開始優化了,看了一下程式,顯然耗時的過程不是對dp求值的過程,因為輸入的多組資料中,不是每組都需要求到n=2000,k=1000的,顯然是在使用memset()給dp賦初值的時候,由於每組資料都要初始化,所以每次都是一個maxn^2的時間,將其改為根據n,k初始化即可,沒有什麼技術含量...

對於空間的優化,空間佔用顯然是因為我無腦的開了一個int dp[maxn][maxn];

我們通過研究程式發現在求解dp[i][j]的過程中,對 i 的值,實際上我們只需要儲存三組就夠了,因為dp[i][j]最多隻會用到dp[i-1]和dp[i-2],對於dp[i-3]和之前的資料是沒有引用的,也就是說這些資料都是無效的了...我們只需要開一個int dp[3][maxn/2];  (k不超過n的一半...)

這樣的陣列叫做“滾動陣列”,相當於在原陣列中每次在求解完dp[i]之後,就把它寫到dp[i-3]那裡,只用3個位置,通過這樣的滾動,就完成了maxn長度的求值,這種技巧在求解dp問題中非常常見。它對於時間上沒有任何幫助,但是在空間上節省的就不是一點半點了(想想2005 * 2005 和 3 * 2005)...

採用“滾動陣列”的技巧,我們順帶的把dp的初始化用時也降低了...只需把原程式中的狀態轉移方程改為如下即可:

dp[i%3][j] = min(dp[(i-1)%3][j], dp[(i-2)%3][j-1] + (a[i] - a[i-1]) * (a[i] - a[i-1]));

改完之後的**如下,紅色部分就是改動內容:

1 #include2 #include3 #include4 #include5 #include6

#define inf 0x3f3f3f3f

7#define maxn 2005

8using

namespace

std;

9int

a[maxn];

10int dp[3][maxn/2];

11int

main()

1221

for (int i = 0; i <= 2; ++i)

2227 dp[i][0] = 0;28

}2930 sort(a + 1, a + n + 1

);31

for (int i = 2; i <= n; ++i)

3237

}38 printf("

%d\n

", dp[n%3

][k]);39}

40return0;

41 }

這樣改完之後,再次提交,時間是 90ms,空間是 240k,已經進入了此題solution排行榜的第一頁,算是比較理想的結果了(對比之前 800ms, 15000k),有興趣的讀者再去對輸入輸出等等細節方面優化一下,衝擊一下best solution吧!

一道有趣的智力題

題目 有12個外觀完全一樣的球,其中有一個球和其他球的重量不一致,如何使用一個天平稱3次得出不一致的球是哪個?筆者看到這題就立馬想到將球分成3組,將其中的兩組進行比較,然後如果不相等,就將重的那組進行兩兩劃分,在比較,在將兩個重的進行比較在進行比較。如果相等則將餘下的那組進行比較。相信這裡有不少園友...

分塊的一道題

題意 區間 k,查詢 c的個數 c一開始給定 1.當k為正數 2.不保證k為正數 題解 兩個的複雜度是不一樣的 1的話顯然每個數只會成為1次c 我們記錄區間比c小的最大值就可以了 每次進入一個區間當且僅當這個區間有 k c的數 複雜度 nlogn 2的話我們考慮分塊 裡面開個陣列維護一下從小到大排列...

一道面試題的思考

在繼承中new和override相同點和區別?看下面的 有一個基類a,b1和b2都繼承自a,並且使用不同的方式改變了父類方法print 的行為。測試 輸出什麼?為什麼?public void dotest public class a public class b1 a public class b...