[数据结构与算法]AcWing 303 运输小猫 题解（动态规划—DP—斜率优化DP）

AcWing 303 运输小猫
斜率优化DP应用题，题解借鉴大佬的：大佬题解
需要注意的细节是，饲养员数量在外层循环，猫的数量在内层循环，这会影响很大的运算速率

#include<bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 1e5 + 10, P = 110;

int n, m, p;
int q[N];
int f[P][N];  //表示M只小猫用P位饲养员运输的最小代价
int d[N], t[N], a[N], s[N];

int get_y(int k, int j){
	return f[j - 1][k] + s[k];
}

signed main()
{
	cin>>n>>m>>p;
	
	for(int i = 2; i <= n; i ++ ){
		cin>>d[i];
		d[i] += d[i - 1];
	}
	
	for(int i = 1; i <= m; i ++ ){
		int h;
		cin>>h>>t[i];
		a[i] = t[i] - d[h];  //a[i]记录接住第i只小猫的最早出发时间 
	}
	
	sort(a + 1, a + 1 + m);
	
	for(int i = 1; i <= m; i ++ ) s[i] = s[i - 1] + a[i];
	
	memset(f, 0x3f, sizeof f);
	for(int i = 0; i <= p; i ++ ) f[i][0] = 0;
	

	for(int j = 1; j <= p; j ++ ){  //p个饲养员 
		int hh = 0, tt = 0;
		q[0] = 0;
		
		for(int i = 1; i <= m; i ++ ){  //m只猫 
			while(hh < tt && (get_y(q[hh + 1], j) - get_y(q[hh], j)) <= a[i] * (q[hh + 1] - q[hh])) hh ++ ;
			int k  = q[hh];
			f[j][i] = f[j - 1][k] - a[i] * k + s[k] + a[i] * i - s[i];
			while(hh < tt && (get_y(q[tt], j) - get_y(q[tt - 1], j)) * (i - q[tt]) >= 
				(get_y(i, j) - get_y(q[tt], j)) * (q[tt] - q[tt - 1])) tt -- ;
			q[ ++ tt] = i;
		}
	}
	cout<<f[p][m]<<endl;
	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖