一站式企业服务,wordpress 页面分类,英文外贸网站建设推广,wordpress更换域名后台登不进去这道题和06年论文《从一类单调性问题看算法的优化》第一道例题很相似。 题意#xff1a;给出n个矿的重量和位置#xff0c;这些矿石只能从上往下运送#xff0c;现在要在这些地方建造m个heap#xff0c;要使得#xff0c;sigma距离*重量最小。 思路#xff1a;O(n ^ 3)的…这道题和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的总重量*距离。 这样我们就可以进行斜率优化了。 所以这一维就降成O1了。那总的复杂度就是On ^ 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 pairint,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
