HDU 1421 搬寝室
首先可以观察到一个结论：肯定是排序完之后每次选择本身就是相邻的数字。
dp[i][j]表示到前i个数字选择了j组的最小花费。
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const long long INF=999999999999999; const int maxn=2200; int n,k; long long a[maxn],dp[maxn][maxn]; int main() { while(~scanf("%d%d",&n,&k)) { for(int i=1; i<=n; i++) scanf("%lld",&a[i]); sort(a+1,a+1+n); for(int i=0;i<=n;i++) for(int j=0;j<=k;j++) dp[i][j]=INF; for(int i=0;i<=n;i++) dp[i][0]=0; for(int i=1;i<=n;i++) { for(int j=1;j<=k;j++) { dp[i][j]=dp[i-1][j]; if(dp[i-2][j-1]==INF) continue; if(i-1==0) continue; dp[i][j]=min(dp[i][j],dp[i-2][j-1]+abs(a[i]-a[i-1])*abs(a[i]-a[i-1])); } } long long ans=INF; for(int i=1;i<=n;i++) ans=min(ans,dp[i][k]); printf("%lld ",ans); } return 0; }