状态转移方程还是很难找啊......
感觉自己分析很不到位，依旧参考了别人的分析......
[cpp]
#include
#include
#include
#include
#include
# define MAX 2005
using namespace std;
int n,k;
int a[MAX];
int dp[MAX][MAX]; //前i个物品中选择j对产生的最小疲劳度
int value(int i,int j)
{
return (i-j) * (i-j);
}
void solve()
{
int i,j;
for(i=2; i<=n; i++)
{
for(j=1; j<=k; j++)
{
if(i == 2 * j)
dp[i][j] = dp[i-2][j-1] + value(a[i],a[i-1]);
else
dp[i][j] = min(dp[i-2][j-1] + value(a[i],a[i-1]), dp[i-1][j]);
}
}
}
int main()
{
int i;
while(cin >> n >> k)
{
for(i=1; i<=n; i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
memset(dp,0,sizeof(dp));
solve();
printf("%d\n",dp[n][k]);
}
return 0;
}
#include
#include
#include
#include
#include
# define MAX 2005
using namespace std;
int n,k;
int a[MAX];
int dp[MAX][MAX]; //前i个物品中选择j对产生的最小疲劳度
int value(int i,int j)
{
return (i-j) * (i-j);
}
void solve()
{
int i,j;
for(i=2; i<=n; i++)
{
for(j=1; j<=k; j++)
{
if(i == 2 * j)
dp[i][j] = dp[i-2][j-1] + value(a[i],a[i-1]);
else
dp[i][j] = min(dp[i-2][j-1] + value(a[i],a[i-1]), dp[i-1][j]);
}
}
}
int main()
{
int i;
while(cin >> n >> k)
{
for(i=1; i<=n; i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
memset(dp,0,sizeof(dp));
solve();
printf("%d\n",dp[n][k]);
}
return 0;
}