专栏文章

题解：P8632 [蓝桥杯 2015 国 B] 居民集会

FFire__Fly
P8632题解参与者 4已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@mipj6cx3
此快照首次捕获于
2025/12/03 12:52
3 个月前
此快照最后确认于
2025/12/03 12:52
3 个月前
查看原文

原题传送门

思路

我们首先用 dpi,jdp_{i,j} 表示在第 ii 个位置一共建立了 jj 个集会点的最小代价，推出暴力公式为 dpi,j=min⁡k=1i−1(dpk,j−1+∑p=k+1i(tp×(di−dp)))dp_{i,j}=\min\limits_{k=1}^{i-1}(dp_{k,j-1}+\sum\limits_{p=k+1}^{i}(t_p\times(d_i-d_p)))，化简为 dpi,j=min⁡k=1i−1(dpk,j−1+di×∑p=k+1itp−∑p=k+1i(tp×dp))dp_{i,j}=\min\limits_{k=1}^{i-1}(dp_{k,j-1}+d_i\times\sum\limits_{p=k+1}^{i}t_p-\sum\limits_{p=k+1}^{i}(t_p\times d_p))，这时我们利用前缀和分别维护 ∑p=k+1itp\sum\limits_{p=k+1}^{i}t_p 和 ∑p=k+1i(tp×dp)\sum\limits_{p=k+1}^{i}(t_p\times d_p) 的值，利用前缀和进行优化，这样我们就可以写出暴力代码。
CPP
#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int dp[maxn][5] , n , l , ll = 1 , rr = 0 , q[maxn] , sumt[maxn] , d[maxn] , t , sumdt[maxn] , f[maxn];
signed main(){
	n = read();
	l = read();
	for(int i = 1; i <= n; i++) {
		d[i] = read();
		t = read();
		sumt[i] = sumt[i - 1] + t;
		sumdt[i] = sumdt[i - 1] + d[i] * t;
	}
	n++;
	d[n] = l;
	sumt[n] = sumt[n - 1];
	sumdt[n] = sumdt[n - 1];
	memset(dp , 0x3f , sizeof(dp));
	dp[1][1] = 0;
	dp[0][0] = 0;
	for(int i = 1; i <= 4; i++) {
		for(int j = 1; j <= n; j++) {
			for(int k = 0; k < j; k++) {
				dp[j][i] = min(dp[j][i] , dp[k][i - 1] + d[j] * (sumt[j] - sumt[k]) - (sumdt[j] - sumdt[k]));
			}
		}
	}
	cout << dp[n][4] << endl;
	return !("wjl1100 qwq");
}
这样我们就可以得到 50 分。
（以下的 dpdp 省掉了第二维）然后我们可以发现这个转移方程可以用斜率优化，我们假设从 kk 转移比从 pp 转移更优且 j>pj > p，那么我们令 gi=dpi+sumdtig_i=dp_i+sumdt_i，则 gj−gpsumtj−sumtp<di\dfrac{g_j-g_p}{sumt_j-sumt_p}<d_i 时可以转移，这时我们发现这个形式非常像斜率公式，所以我们用 gig_i 为纵坐标，sumtisumt_i 作横坐标做斜率优化，枚举转移点，找到满足要求且编号最大的点进行转移，又因这里为小于，所以用单调队列维护下凸壳即可。
CPP
#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int dp[maxn][5] , n , l , ll = 1 , rr = 0 , q[maxn] , sumt[maxn] , d[maxn] , t , sumdt[maxn];
inline int getg(int i , int k) {
	return dp[i][k] + sumdt[i];
}
inline long double getxl(int i , int j , int k) {
	if(sumt[i] == sumt[j]) return inf;
	return (long double) (getg(j , k) - getg(i , k)) / (sumt[j] - sumt[i]);
}
signed main(){
	n = read();
	l = read();
	for(int i = 1; i <= n; i++) {
		d[i] = read();
		t = read();
		sumt[i] = sumt[i - 1] + t;
		sumdt[i] = sumdt[i - 1] + d[i] * t;
	}
	n++;
	d[n] = l;
	sumt[n] = sumt[n - 1];
	sumdt[n] = sumdt[n - 1];
	memset(dp , 0x7f , sizeof(dp));
	dp[0][0] = 0;
	for(int time = 1; time <= 4; time++) {
		ll = 1;
		rr = 0;
		q[++rr] = 0;
		for(int i = 1; i <= n; i++) {
			while(rr > ll && getxl(q[ll] , q[ll + 1] , time - 1) <= d[i]) ll++;
			int u = q[ll];
			dp[i][time] = dp[u][time - 1] + d[i] * (sumt[i] - sumt[u]) - (sumdt[i] - sumdt[u]);
			while(rr > ll && getxl(q[rr - 1] , q[rr] , time - 1) >= getxl(q[rr] , i , time - 1)) rr--;
			q[++rr] = i;
		}
	}
	cout << dp[n][4] << endl;
	return !("wjl1100 qwq");
}
三倍经验：
居民集会
仓库建设
锯木厂选址

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...