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

· · 题解

原题传送门

思路

我们首先用 dp_{i,j} 表示在第 i 个位置一共建立了 j 个集会点的最小代价，推出暴力公式为 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)))，化简为 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))，这时我们利用前缀和分别维护 \sum\limits_{p=k+1}^{i}t_p 和 \sum\limits_{p=k+1}^{i}(t_p\times d_p) 的值，利用前缀和进行优化，这样我们就可以写出暴力代码。

#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 分。

（以下的 dp 省掉了第二维）然后我们可以发现这个转移方程可以用斜率优化，我们假设从 k 转移比从 p 转移更优且 j > p，那么我们令 g_i=dp_i+sumdt_i，则 \dfrac{g_j-g_p}{sumt_j-sumt_p}<d_i 时可以转移，这时我们发现这个形式非常像斜率公式，所以我们用 g_i 为纵坐标，sumt_i 作横坐标做斜率优化，枚举转移点，找到满足要求且编号最大的点进行转移，又因这里为小于，所以用单调队列维护下凸壳即可。

#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");
}

三倍经验：

居民集会

仓库建设

锯木厂选址