1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <iostream> 6 using namespace std; 7  8 #define MAXN 5005 9 #define MAXK 100510 #define INF 0x3f3f3f3f11 int a[MAXN];12 int s[MAXN];13 int dp[MAXN][MAXK];14 15 int main() {16     int n, K, t;17     int i, j, k;18 19 #ifndef ONLINE_JUDGE20     freopen("data.in", "r", stdin);21 #endif22 23     scanf("%d", &t);24     while (t--) {25         scanf("%d %d", &K, &n);26         K += 8;27         for (i=1; i<=n; ++i)28            scanf("%d", &a[i]);29         for (i=1; i<n; ++i)30             s[i] = (a[i+1]-a[i])*(a[i+1]-a[i]);31         memset(dp, 0x3f, sizeof(dp));32         for (i=0; i<=n; ++i)33             dp[i][0] = 0;34         for (j=1; j<=K; ++j) {35             for (i=n+1-3*j; i>0; --i) {36                 dp[i][j] = min(dp[i][j], dp[i+2][j-1]+s[i]);37                 dp[i][j] = min(dp[i][j], dp[i+1][j]);38             }39         }40         int ans = INF;41         for (j=1; j<=n; ++j)42             if (dp[j][K] < ans)43                 ans = dp[j][K];44         printf("%d\n", ans);45     }46 47     return 0;48 }