C++11(clang++ 3.9) 解法, 执行用时: 63ms, 内存消耗: 71108K, 提交时间: 2020-06-19 22:58:14

#pragma GCC optimize(2)
#include <cstdio>
#include <queue>
#include <string>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <fstream>
#include <cassert>
#include <complex>
#include <ctime>
#include <tr1/unordered_map>
#include <bitset>

using namespace std;
using namespace tr1;
typedef long long ll;
inline int read()
{
    int x = 0;
    int f = 0;
    char ch = 0;
    while(!isdigit(ch))
    {
        f |= (ch == '-') ? 1 : 0;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return f ? -x : x;
}

const ll INF = 1e17;
const int maxn = 3e3 + 10;
ll dp[maxn][maxn];
ll tmp1[maxn];
ll tmp2[maxn];
ll aa[maxn];
int n;

int main()
{
    n = read();
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= 3000; ++j)
            dp[i][j] = INF;
    for(int i = 1; i <= n; ++i)
        aa[i] = read();
    for(int i = 1; i <= 3000; ++i)
        dp[1][i] = (ll)(i - aa[1]) * (i - aa[1]);
    for(int i = 1; i <= n; ++i)
    {
        if(i >= 2)
        {
            for(int j = 1; j <= 3000; ++j)
            {
                dp[i][j] = tmp1[j] + (ll)(aa[i] - j) * (aa[i] - j);
            }
        }
        if(i <= n - 1)
        {
            tmp1[0] = INF;
            for(int j = 1; j <= 3000; ++j)
            {
                tmp1[j] = min(tmp1[j - 1],dp[i][j]);
            }
        }
    }
    /*for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= 10; ++j)
            printf("%lld ",dp[i][j]);
        printf("\n");
    }*/
    ll ans = INF;
    for(int i = 1; i <= 3000; ++i)
        ans = min(ans,dp[n][i]);
    printf("%lld",ans);
}

C++14(g++5.4) 解法, 执行用时: 57ms, 内存消耗: 71008K, 提交时间: 2019-10-26 20:18:40

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long

const double eps=1e-8;
const ll inf=1e9;
const ll mod=1e9+7;
const int maxn=3e3+10;
int v=3000;

ll a[maxn],f[maxn][maxn];

int main()
{
    int n,i,j;
    ll k,r;
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    f[0][1]=0;
    for (i=1;i<=n;i++)
    {
        k=1e18;
        for (j=1;j<=v;j++)
        {
            k=min(k,f[i-1][j]);
            f[i][j]=k+(a[i]-j)*(a[i]-j);
        }
    }
    r=1e18;
    for (j=1;j<=v;j++)
        r=min(r,f[n][j]);
    printf("%lld",r);
    return 0;
}