是式子推错了还是代码写错了？
查看原帖
是式子推错了还是代码写错了？
549131
Eous楼主2025/1/8 16:14

式子：

dpi=min⁡(dpj+a×(sumi−sumj)2+b×(sumi−sumj)+c)=min⁡(dpj+a×sumi2+a×sumj2−2a×sumisumj+b×sumi−b×sumj+c)=a×sumi2+b×sumi+c+min⁡(dpj+a×sumj2−b×sumj−2a×sumisumj) xj=sumjyj=dpj+a×sumj2−b×sumjki=−2a×sumibi=dpi−(a×sumi2+b×sumi+c)\begin{aligned} dp_{i} & = \min(dp_{j} + a \times (sum_{i} - sum_{j})^{2} + b \times (sum_{i} - sum_{j}) + c) \\ & =\min(dp_{j} + a \times sum_{i}^{2} + a \times sum_{j}^{2} - 2a \times sum_{i}sum_{j} + b \times sum_{i} - b \times sum_{j} + c) \\ & = a \times sum_{i}^{2} + b \times sum_{i} + c + \min(dp_{j} + a \times sum_{j}^{2} - b \times sum_{j} - 2a \times sum_{i}sum_{j}) \end{aligned} \\ \ \\ \begin{aligned} x_{j} & = sum_{j} \\ y_{j} & = dp_{j} + a \times sum_{j}^{2} - b \times sum_{j} \\ k_{i} & = -2a \times sum_{i} \\ b_{i} & = dp_{i} - (a \times sum_{i}^{2} + b \times sum_{i} + c) \end{aligned}

代码：

#include<bits/extc++.h>
#define int long long
#define sq(x) ((x) * (x))
using namespace std;
const int maxn = 1e6 + 5;
int n,a,b,c;
int sum[maxn],dp[maxn];
int q[maxn],head,tail;
int x(int i){return sum[i];}
int y(int i){return dp[i] + a * sq(sum[i]) - b * sum[i];}
int k(int i){return -2 * a * sum[i];}
long double slope(int i,int j){return (long double)(y(j) - y(i)) / (x(j) - x(i));}
signed main()
{
    scanf("%lld",&n);
    scanf("%lld%lld%lld",&a,&b,&c);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld",sum + i);
        sum[i] += sum[i - 1];
    }
    head = tail = 1;
    q[1] = 0;
    for (int i = 1,j; i <= n; i++)
    {
        while (tail > head && slope(q[head],q[head + 1]) <= k(i))
            head++;
        j = q[head];
        dp[i] = dp[j] + a * sq(sum[i] - sum[j]) + b * (sum[i] - sum[j]) + c;
        while (tail > head && slope(q[tail - 1],q[tail]) > slope(q[tail],i))
            tail--;
        q[++tail] = i;
    }
    printf("%lld",dp[n]);
    return 0;
}
2025/1/8 16:14