0pts求条
查看原帖
0pts求条
549131
Eous楼主2025/1/10 15:52
#include<bits/extc++.h>
#define int long long
#define sq(x) ((x) * (x))
using namespace std;
typedef long double ld;
const int maxn = 3005;
int n,m;
int dis[maxn];
int dp[maxn][maxn];
int q[maxn],head,tail;
int K(int i){return 2 * m * dis[i];}
int x(int k){return dis[k];}
int y(int k,int j){return dp[k][j - 1] + m * sq(dis[k]);}
ld slope(int i,int k,int j){return ((ld)y(i,j) - (ld)y(k,j)) / ((ld)x(i) - (ld)x(k));}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld",dis + i);
        dis[i] += dis[i - 1];
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0][0] = 0;
    for (int j = 1; j <= m; j++)
    {
        head = tail = 1;
        q[1] = j - 1;
        for (int i = j; i <= n; i++)
        {
            while (tail > head && slope(q[head + 1],q[head],j) < K(i))
                head++;
            int k = q[head];
            dp[i][j] = dp[k][j - 1] + m * sq(dis[i] - dis[k]) - 2 * (dis[i] - dis[k]) * dis[n];
            while (tail > head && slope(q[tail],q[tail - 1],j) > slope(i,q[tail],j))
                tail--;
            q[++tail] = i;
        }
    }
    printf("%lld",dp[n][m] + sq(dis[n]));
    return 0;
}

或者帮我看看柿子有没有推错：

dpi,j=min⁡k<i{dpk,j−1+m×(disi−disk)2−2(disi−disk)×disn}=min⁡{dpk,j−1+m×(disi2+disk2−2disidisk)−2(disi−disk)×disn}=min⁡{dpk,j−1+m×disi2+m×disk2−2m×disidisk−2(disi−disk)disn}=m×disi2−2(disi−disk)disn+min⁡{dpk,j−1+m×disk2−2m×disidisk}k=2m×disix=diskb=dpi,j−m×disi2+2(disi−disk)disny=dpk,j−1+m×disk2\begin{aligned} dp_{i,j} & = \min _ {k \lt i}\{dp_{k,j - 1} + m \times (dis_{i} - dis_{k})^{2} - 2(dis_{i} - dis_{k}) \times dis_{n} \} \\ & = \min\{dp_{k,j - 1} + m \times (dis_{i}^{2} + dis_{k}^{2} - 2dis_{i}dis_{k}) - 2(dis_{i} - dis_{k}) \times dis_{n} \} \\ & = \min\{dp_{k,j - 1} + m \times dis_{i}^{2} + m \times dis_{k}^{2} - 2m \times dis_{i}dis_{k} - 2(dis_{i} - dis_{k})dis_{n} \} \\ & = m \times dis_{i}^{2} - 2(dis_{i} - dis_{k})dis_{n} + \min\{dp_{k,j - 1} + m \times dis_{k}^{2} - 2m \times dis_{i}dis_{k} \} \end{aligned} \\ \begin{aligned} k & = 2m \times dis_{i} \\ x & = dis_{k} \\ b & = dp_{i,j} - m \times dis_{i}^{2} + 2(dis_{i} - dis_{k})dis_{n}\\ y & = dp_{k,j - 1} + m \times dis_{k}^{2} \end{aligned}\\
2025/1/10 15:52