Vijos 1061 迎春舞会之三人组舞(DP)

经典DP问题，通过问题，看出结论，然后倒序，然后注意条件。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 #define INF 100000000
 8 int dp[5001][5001];
 9 int p[5001];
10 bool cmp(int a,int b)
11 {
12     return a > b;
13 }
14 int main()
15 {
16     int n,m,i,j;
17     scanf("%d%d",&m,&n);
18     for(i = 1;i <= n;i ++)
19     scanf("%d",&p[i]);
20     sort(p+1,p+n+1,cmp);
21     for(i = 1;i <= n;i ++)
22     {
23         for(j = 1;j <= m;j ++)
24         dp[i][j] = INF;
25     }
26     for(i = 3;i <= n;i ++)
27     {
28         for(j = 1;j <= m;j ++)
29         {
30             if(i >= 3*j)
31             dp[i][j] = min(dp[i-1][j],dp[i-2][j-1] + (p[i]-p[i-1])*(p[i]-p[i-1]));
32         }
33     }
34     printf("%d
",dp[n][m]);
35     return 0;
36 }