六级考生报道

前情提要

当时我也不清楚怎么AC的了，我妈说考不过就不让我打三角洲了，所以超常发挥写出来的，现在都读不懂自己写的了。。。

分割线

就是遍历一整个数组，然后每次都降外必先安内。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a[2010],n,dp[2010];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,0x3f3f3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+a[i]*a[i];
        int sum=0;
        for(int j=i;j>=1;j--){
            sum+=a[j];
            dp[i]=min(dp[i],dp[j-1]+sum*sum);
        }
    }
    cout<<dp[n];
    return 0;
}