时隔多日，又回来啃dp...

题意：有n件物品，搬k次，每搬一个消耗的疲劳值为两件物品重量之差的平方，求最小的疲劳消耗

状态转移方程：dp[i][j] = min((dp[i-2][j-1]+(s[i]-s[i-1])*(s[i]-s[i-1])),dp[i-1][j]);

dp[i][j]表示有i个物品时j次搬运最小的疲劳值

 

#include
    
     #include
     
      #include
      
       using namespace std;#define INIT 2147483646int dp[2222][1111];int main(){    int i,j,k,n;    int s[2222] = {0};    while(cin>>n>>k){        for(i=1;i<=n;i++)            scanf("%d",s+i);        sort(s+1,s+n+1);        dp[0][0] = 0;        for(i=0;i<=n;i++)            for(j=1;j<=k;j++)                dp[i][j] = INIT;        for(i=2;i<=n;i++)            for(j=1;j*2<=i;j++)                dp[i][j] = min((dp[i-2][j-1]+(s[i]-s[i-1])*(s[i]-s[i-1])),dp[i-1][j]);        cout<
       
        <