K - 摩天輪

Time Limit: 10000/4000MS (Java/Others) ??? Memory Limit: 262143/262143KB (Java/Others)

Submit?Status

一天，冬馬被春希和雪菜拉著去一起去游樂園玩。

經(jīng)過了各種過山車的洗禮后，三人決定去坐摩天輪休息下。

這是一個巨大的摩天輪，每一個車廂能坐任意多的人。現(xiàn)在，等著坐摩天輪的有n個人(包含他們3人)，摩天輪還有m個車廂可以坐人。每個人都有自己肥胖程度，出于某些原因，胖子和瘦子坐在同一節(jié)車廂就會產(chǎn)生一定的矛盾，這個矛盾的值為(MAX?MIN)2，其中MAX為當(dāng)前車廂里面最胖的人的肥胖程度，MIN為最廋的那個人的肥胖程度。

愛管閑事的春希當(dāng)然不希望就因為這點小事而使大家的這趟旅途不愉快，于是他決定幫大家安排怎么坐才能使總的矛盾值最小，希望你能幫他找到這個最小的矛盾值

Input

第一行為兩個整數(shù)n，m，分別表示人數(shù)和車廂數(shù)。(3≤n≤10000,1≤m≤5000)

第二行為n個整數(shù)，wi表示第i個人的肥胖程度。(0≤wi≤1000000)

Output

每組數(shù)據(jù)，輸出一個整數(shù)，為矛盾的最小值。（答案保證小于231）

Sample input and output

Sample InputSample Output

4 2 4 7 10 1	18

?

解題思路:

這是一道斜率優(yōu)化DP的題目.

?我們令 f ( i , j ) 表示將前 i 個人分成 j 份所需的最小費用.

F ( i , j ) = min{ F ( u , j -1) + (sum[i] – sum[ u + 1])^2 }

但是這樣做的復(fù)雜度高達O(N^2*M),對于本題的規(guī)模來講無法承受，我們考慮

K1 < k2 < i ,且 k2 比 k1更優(yōu)

有式子

?F ( k2 , j - 1 ) + sum( k2 ) ^ 2 -? F( k1 , j -1 ) – sum(k1+1) ^ 2

?—————————————————————?—————————————?? < 2 * sum(i)

???????????? sum ( k2 ) – sum( k1+1)

顯然這是一個斜率的式子.

假設(shè)現(xiàn)在 K(k1 – k2) < 2*sum[i] ,那么k1這個點還有價值嗎？

我們注意到sum[i]是單調(diào)不減的，也就是說,對于之后的i2,i3…..

K(k1 – k2) < 2*sum[i_x] ,也就是說，k1 完全不可能成為某個點的最優(yōu)解了，是可以舍棄的.

那么如果現(xiàn)在有 K(k1 – k2) >= 2*sum[i]呢，目前顯然是選擇k1比k2好，我們應(yīng)不應(yīng)該舍棄k2呢？答案是不應(yīng)該，因為隨著i的增大，sum[i]是不減的（也就是說，sum[i]可能會增大）,此時 K(k1 – k2) < 2*sum[i] 是可能成立的.

綜上所述，我們維護一個單調(diào)隊列即可，只不過這個單調(diào)隊列剔除 / 加入元素的條件都是和與斜率有關(guān)，這樣我們可以在O(1)的時間內(nèi)得到某個點的最優(yōu)決策點,復(fù)雜度成功降到了O(n*m).

?

代碼使用了滾動數(shù)組進行優(yōu)化

#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn = 1e4 + 50; int n,m,h[maxn],f[2][maxn],cur=0,q[maxn];double slope(int x,int y) {if (h[x+1] == h[y+1])return 1e233;return (double)(f[cur^1][x] + h[x+1]*h[x+1] - (f[cur^1][y] + h[y+1]*h[y+1])) / (double)(h[x+1] - h[y+1]); }int main(int argc,char *argv[]) {scanf("%d%d",&n,&m);for(int i = 1 ; i <= n ; ++ i) scanf("%d",&h[i]);sort(h+1,h+1+n);for(int i = 1; i <= n ; ++ i) f[cur][i] = (h[i]-h[1])*(h[i]-h[1]);for(int i = 2 ; i <= m ; ++ i){cur ^= 1;int front = 0 , rear = 0 ;q[rear++] = 1;for(int j = 2 ; j <= n ; ++ j){while (rear - front > 1 && slope(q[front],q[front+1]) <= 2*h[j])front++;f[cur][j] = f[cur^1][q[front]] + (h[j] - h[q[front]+1])*(h[j] - h[q[front]+1]);while(rear - front > 1 && slope(q[rear-2],q[rear-1]) >= slope(q[rear-1],j))rear--;q[rear++] = j;}}printf("%d\n",f[cur][n]);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Xiper/p/4539638.html

總結(jié)

以上是生活随笔為你收集整理的UESTC_摩天轮 2015 UESTC Training for Dynamic ProgrammingProblem K的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。