损失

【题目描述】

小苯有两个机器人在数轴上移动。初始时，两个机器人都位于位置 0。

数轴上会依次出现 n 个任务点，第 i 个任务点的坐标为 pi。

对于每个任务点，小苯必须选择其中一个机器人移动到该任务点（另一个机器人保持原地不动），并执行任务。

机器人移动的代价等于移动的距离，即从位置 x 移动到 y 的代价为 |x − y|。

小苯必须严格按照时间顺序（从第 1 个任务点到第 n 个任务点）依次执行所有任务。

你的任务就是求出：执行完所有 n 个任务所需的最小总代价。

【输入格式】

每个测试文件均包含多组测试数据。第一行输入一个整数 T (1 ≤ T ≤ 10) 代表数据组数。

对于每组测试数据：第一行输入一个整数 n (1 ≤ n ≤ 5000)，代表任务点的数量。

第二行输入 n 个整数 p1, p2, . . . , pn (1 ≤ pi ≤ 109)，代表任务点的坐标。

【输出格式】

对于每组测试数据，输出一个整数，表示最小总代价。

【样例输入】

2

3

1 2 3

4

1 5 2 8

【样例输出】

3

10

#include<iostream>
#include<cstdlib>
using namespace std;

int main(){
    int T;
    cin>>T;
    while(T--){
        long long int n;
        cin>>n;
        long long int* p =new long long int[n+1]();
        long long int* a =new long long int[n]();
        for(long long int i=0;i<n;i++){
            cin>>p[i+1];
            if(i==0){
                a[i]=p[1];
            }else{
                long long int min=a[0]+p[i+1];
                for(int j=1;j<i;j++){
                    long long int temp=a[j]+labs(p[j]-p[i+1]);
                    if(min>temp){
                        min=temp;
                    }
                }
                a[i]=min;
                for(long long int j=0;j<i;j++){
                    a[j]+=labs(p[i+1]-p[i]);
                }
            }
        }
        long long int total=a[0];
        for(long long int i=1;i<n;i++){
            if(total>a[i]){
                total=a[i];
            }
        }delete[] p;
        delete[] a;
        printf("%lld\n",total);
    }return 0;
}