求大佬帮忙看一下
查看原帖
求大佬帮忙看一下
1277540
masirui楼主2024/8/11 18:02

求大佬帮我看一下,最后一个点过不了

#include<bits/stdc++.h>
#define int unsigned long long
#define double long double
using namespace std;

const int SIZE = 1e6 + 5;
const int inf = 1e9 + 7;

struct  node{
    int cost, cnt, dis;
}ori[SIZE];

int n, l, r;
int c[SIZE], d[SIZE], w[SIZE], dp[SIZE], q[SIZE], m[SIZE];

int X(int i){ return c[i]; }
int Y(int i){ return dp[i] + m[i]; }
double slope(int i, int j){
    if(X(i) == X(j))    return inf;
    return (double)((Y(j) * 1.0 - Y(i)) / (X(j) * 1.0 - X(i)));
}

signed main(){
    ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)    cin >> d[i] >> c[i] >> w[i], m[i] = d[i] * c[i];
    for(int i = 1; i <= n; i ++)    c[i] += c[i - 1], m[i] += m[i - 1];
    l = 1, q[++ r] = 0;
    for(int i = 1; i <= n; i ++){
        while(l < r && slope(q[l], q[l + 1]) <= d[i]) l ++;
        dp[i] = dp[q[l]] + (c[i] - c[q[l]]) * d[i] - (m[i] - m[q[l]]) + w[i];
        while(l < r && slope(q[r - 1], q[r]) >= slope(q[r], i)) r --;
        q[++ r] = i;
    }
    // memset(dp, 0x3f, sizeof dp);
    // dp[0] = 0;
    // for(int i = 1; i <= n; i ++){
    //     for(int j = 0; j < i; j ++){
    //         dp[i] = min(dp[i], dp[j] + (c[i] - c[j]) * d[i] - (m[i] - m[j]) + w[i]);
    //     }
    // }
    int ans = dp[n], i = n;
    while(i && c[i] - c[i - 1] == 0)  ans = min(ans, dp[-- i]);
    cout << ans << '\n';
    return 0;
}
2024/8/11 18:02
加载中...