這道題和06年論文《從一類單調性問題看算法的優化》第一道例題很相似。

題意：給出n個礦的重量和位置，這些礦石只能從上往下運送，現在要在這些地方建造m個heap，要使得，sigma距離*重量最小。

思路：O(n ^ 3)的DP解法是很容易想出來的。

dp[i][j] 表示第i個礦石點是j個heap的最小花費。

dp[i][j] = min(dp[i][j] , dp[k][j - 1] + sigma(sum[i] - sum[k])) 。

其中i , j , k 分別要一重循環，所以復雜度達到10 ^ 9。

這顯然是TLE的，所以需要優化。

我們可以來看狀態轉移方程，dp[i][j] = dp[k][j - 1] +( sum1[i] - sum1[k] ) * a[i] - (sum2[i] - sum2[k]) .其中sum1是1到i的總重量，sum2表示1到i的總重量*距離。

這樣，我們就可以進行斜率優化了。

所以這一維就降成O（1）了。那總的復雜度就是O（n ^ 2）。

?

#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x7ffffffffffffll #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )using namespace std;#define N 1111ll sum1[N] ; ll sum2[N] ; ll dp[N][N] ; int qe[N] ; ll a[N] , b[N] ; int n , m ; //分子 ll getU(int j , int k , int z){return dp[k][j - 1] + sum2[k] - (dp[z][j - 1] + sum2[z]) ; } //分母 ll getD(int k , int z){return sum1[k] - sum1[z] ; }ll getDP(int i ,int j ,int k){return dp[k][j - 1] + (sum1[i] - sum1[k]) * a[i] - (sum2[i] - sum2[k]) ; }int main() {while(cin >> n >> m){for (int i = 1 ; i <= n ; i ++ )cin >> a[i] >> b[i] ;sum1[0] = sum2[0] = 0 ;for (int i = 1 ; i <= n ; i ++ ){sum1[i] = sum1[i - 1] + b[i] ;sum2[i] = sum2[i - 1] + a[i] * b[i] ; // cout << sum1[i] << " " << sum2[i] << endl;}for (int i = 0 ; i <= n ; i ++ )for (int j = 0 ; j <= m ; j ++) dp[i][j] = inf ;dp[0][0] = 0 ;for (int j = 1 ; j <= m ; j ++ ){int head = 0 , tail = 0 ;qe[tail ++ ] = 0 ;for (int i = 1 ; i <= n ; i ++ ){while(head + 1 < tail && getU(j , qe[head + 1] , qe[head]) <= a[i] * getD(qe[head + 1] , qe[head]))head ++ ;dp[i][j] = getDP(i , j , qe[head]) ;while(head + 1 < tail && getU(j , i , qe[tail - 1]) * getD(qe[tail - 1] ,qe[tail - 2]) <=getU(j , qe[tail - 1] , qe[tail - 2]) * getD(i , qe[tail - 1]))tail -- ;qe[tail ++ ] = i ;}}cout << dp[n][m] << endl ;}return 0 ; }

?

?

轉載于:https://www.cnblogs.com/suncoolcat/p/3301700.html

總結

以上是生活随笔為你收集整理的UVAlive 6131 dp+斜率优化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。