题意分析

给定一个长度为$N$的整数序列$A$，需要构造一个长度相同的序列$B$，使得以下两部分之和$V$最小：

1. $A$与$B$的绝对差之和：$\sum_{i=1}^{N} |A(i) - B(i)|$
2. $B$序列相邻元素的绝对差之和：$\sum_{i=1}^{N-1} |B(i) - B(i+1)|$

解题思路

1. 问题分解：
   • 第一部分要求$B$尽可能接近$A$（使$|A(i)-B(i)|$最小）
   • 第二部分要求$B$序列尽可能平滑（使相邻元素变化$|B(i)-B(i+1)|$最小）
2. 关键观察：
   • 最优解中$B(i)$的取值范围应在$A$序列的最小值和最大值之间
   • 可通过动态规划求解，状态设计需考虑当前$B(i)$的取值对后续的影响

实现步骤

1. 预处理：
   • 确定$A$序列的最小值$min\_A$和最大值$max\_A$
   • 枚举$B(i)$的可能取值范围（$min\_A$到$max\_A$）
2. 动态规划：
   • 定义$dp[i][j]$表示处理到第$i$个元素时$B(i)=j$的最小$V$值
   • 状态转移方程：
     $dp[i][j] = |A(i)-j| + \min_{k} (dp[i-1][k] + |k-j|)$
3. 结果提取：
   • 最终结果为$\min_{j} dp[N][j]$

代码实现

#include<stdio.h>
#include<string.h>
#include<math.h>
#define INF 0x3fffffff
#include<iostream>
using namespace std;
int mad(int a,int b,int c)
{//取三个数的中间值
    int ma=a,mi=a;
    ma=max(a,b);
    ma=max(ma,c);
    mi=min(a,b);
    mi=min(mi,c);
    return a+b+c-mi-ma;
}
int main()
{
    int a[1000];
    int b[1000];
    int  n;
    int s=0;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    for(int i=1; i<n-1; i++)
    {
        b[i]=mad(b[i-1],a[i],b[i+1]);
    }
    for(int i=0; i<n; i++)
    {
        s+=fabs(a[i]-b[i]);
    }
    for(int i=1; i<n; i++)
        s+=fabs(b[i]-b[i-1]);
    printf("%d\n",s);
    return 0;
}