学步园

小记：最开始想的太简单了，对差值排序，从小到大把能选的都选了就以为是答案了。虽然一开始我觉得是dp，但是被这个思想左右了，就错下去了。 WA几次后，彻底觉悟了，这个方法不行，看discuss里有dp解的，立马转向dp思路，终于被我想到了转移方程， 边界处理wa了我一次。

思路：dp，首先我们将得到的物品的重量从小到大排个序，然后从小到大依次计算出两两之间的差值的平方，保存到数组p[]里。

dp[i][j][0] 代表在前j个差值里，搬i对（每一个差值代表一对），但是不包括第j个差值的最小疲劳度

dp[i][j][1] 代表在前j个差值里，搬i对（每一个差值代表一对），而且包括第j个差值的最小疲劳度

状态转移方程：

dp[i][j][0] = min(dp[i][j-1][0], dp[i][j-1][1]) ( j >= 2*i-1)

dp[i][j][1] = min(dp[i-1][j-2][0], dp[i-1][j-2][1]) + p[i]  （j >= 2*i-1）(保证前j个差值能找出i对)

最后的answer就是min(dp[k][n-1][0], dp[k][n-1][1])

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 1010;
const int N = 100010;
const int INF = 0x7fffffff;

int a[MAX_*2];

int dp[MAX_][MAX_*2][2];
int n, k, ans;


int main(){

	while(scanf("%d%d",&n,&k) != EOF){
        for(int i = 1; i <= n; ++i){
            scanf("%d", &a[i]);
        }

        sort(a+1,a+n+1);

        for(int i = 2; i <= n; ++i ){
            a[i-1] = a[i] - a[i-1];
            a[i-1] *= a[i-1];
        }

        for(int i = 0; i <= k; ++i){
            for(int j = 0; j <= n-1; ++j){
                dp[i][j][0] = INF;
                dp[i][j][1] = INF;
            }
        }

        for(int i = 1; i <= k; ++i){
            for(int j = 2*i-1; j <= n-1; ++j){
                dp[i][j][0] = min(dp[i][j-1][1], dp[i][j-1][0]);
                if(j - 2 >= 0)
                    dp[i][j][1] = min(dp[i-1][j-2][0], dp[i-1][j-2][1]);
                if(dp[i][j][1] == INF)
                    dp[i][j][1] = a[j];
                else dp[i][j][1] += a[j];
            }
        }

        ans = min(dp[k][n-1][0], dp[k][n-1][1]);
        printf("%d\n",ans);
	}
	return 0;
}

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define eps 10e-8

const int MAX_ = 1001;
const int N = 100010;
const int INF = 0x7fffffff;


int dp[MAX_][MAX_*2][2];

int a[MAX_*2];


int main() {
    int n, T, k;

    while(~scanf("%d%d", &n, &k)){
        for(int i = 1; i <= n; ++i){
        	scanf("%d", &a[i]);
        }
        sort(a+1,a+n+1);

        for(int i = 1; i <= k; ++i){
            for(int j = 0; j < n; ++j){
                dp[i][j][0] = INF;
                dp[i][j][1] = INF;
            }
        }

        for(int i = 2; i <= n; ++i){
        	a[i-1] = a[i] - a[i-1];
        	a[i-1] *= a[i-1];
        }

        for(int j = 1; j <= k; ++j){
            for(int i = 2*j - 1; i < n; ++i){
                dp[j][i][0] = min(dp[j][i-1][0], dp[j][i-1][1]);
                if(j > 1)
                    dp[j][i][1] = min(dp[j-1][i-2][0], dp[j-1][i-2][1]) + a[i];
                else dp[j][i][1] = a[i];
            }
        }

        printf("%d\n", min(dp[k][n-1][1], dp[k][n-1][0]));
    }
    return 0;
}