2017百度校招筆試第一題

題意：

大概是一個小朋友去遊樂園，遊樂園一個有 n 個項目，第i項目需要花費 a[i] 時間去玩，小朋友的門票一共可以在遊樂園裡面待 t 時間，隻要在這個時間内開始一個項目，那麼他可以等到項目結束後才離開遊樂園。問他能玩的項目時間總和最大是多少？

其中：n<=100,t<=10000000,a[i]<=100

分析：

定義： dp[n][t] 表示小朋友前 n 個項目中，一共玩了t時間，他需要的門票的最短時間。

由此可以知道轉移方程為：

dp[n][t]=min(dp[n−1][t],t−max{a[i]|i為所有被選擇的項目的腳标}+1)

容易看出來，後面更新的一塊是一個很難解決的過程。如果 a[n] 是最大值，那麼方程就變成了：

dp[n][t]=min(dp[n−1][t],t−a[n]+1)

但是 a[n] 可能不是最大值？這個時候裡面的那部分更新起來非常麻煩。

這個時候，如果我們對原序列進行一次排序， 從小到大，那麼我每一次更新的 a[n] 就會變成之前所有序列裡面的最大值，然後題目就做完了。

複雜度： o(n∗n∗max{a[i]})