本文共 765 字，大约阅读时间需要 2 分钟。
题目：
对每相邻的一对取或者不取
#include #include #include #include #include #include #include #include #include #include #include using namespace std;const int INF=0xfffffff;int Min(int a,int b){ return a>b?b:a;}int a[2222];int dp[2222][1111];int main(){ int n,k; while(scanf("%d%d",&n,&k)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++) for(int j=1;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=0;j<=i/2;j++){ dp[i][j]=Min(dp[i-1][j],dp[i-2][j-1]+(a[i]-a[i-1])*(a[i]-a[i-1])); } } printf("%d\n",dp[n][k]); } return 0;}
转载于:https://www.cnblogs.com/yigexigua/p/3782008.html