这是一道中文题！终于是中文的了！
题目大意:
小明搬家，有n(2000)个东西,小明选择2*k个东西搬过去，然后他 还特别懒。然后他根据多年的经验发现，搬东西获得的疲劳度为左手和右手所搬东西的重量差的平方。（这小明可真是个人才~）现在， 给你这n个东西的重量，以及要选的东西个数k，问你最少的疲劳度为多少。

思路：小明的这个经验很阴险啊，为什么疲劳度是平方而不是绝对值呢，就是因为，如果是绝对值就可以贪心了但是平方之后，它是非线性的，这样就会出现。也许每次选差距最小的两个不会是最优，因为是有可能选了差距最小的两个之后，就会影响到其他的选取。例如：a<b<c<d。如果bc之间最短，但是选完bc之后，只能再选ad了 。这就不如选ab，然后cd。然后就想到要三维dp，但是首先是时间复杂度O(n^3)显然超时了，而且确实十分不好处理，所占在空间也不小。根据据所给数据的规模，我猜时间复杂度为O(n^2)，也就是二维dp。k算是其中一维的话，剩下的另一维就一定要是ij的结合。所以想到是否 可以优化ij。

猜想：如果把这n个物品的重量从小到大排序，那么，每次选取的两个物品一定是相邻的！
下面证明：
要证明猜想只要证明 ：对于含有重量关系e<a<b<c<d的物品不会存在最优选取方案包含a，c。
1.若b没有被搬走，那么，搬ac一定不会优于搬min（ab,bc）。
2.若b被搬走了，那么，假设和b一起被搬走的为d（e也同理）。那么可以通过代数证明：(a-c)^2+(b-d)^2>=(a-b)^2+(c-d)^2;这也就是说 ，搬ac和bd，一定不如搬ab，cd。证毕~

dp建立：

设v[i]表示选第i个和第i+1个物品所得的疲劳度。m[i][k]表示在前i+1个物品中选出k组物品，所获得的最小疲劳度。

递推关系:m[i][k]=min(m[i-2][k-1]+v[i],m[i-1][k]);

边界条件:m[i][1],m[1][k],m[0][k]。


#include #include #include #include #define N 2500 #define K 1200 #define inf 9220372036854775807 using namespace std; int n,k; long long int a[N]={0}; long long int v[N]={0}; long long int m[N][K]={0}; void input() { for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } } void init() { for(int i=1;im[i][k])min=m[i][k]; } return min; } void ceshi() { for(int i=0;i<=10;i++) { for(int j=0;j<=10;j++) { cout<>n>>k) { input(); sort(a+1,a+n+1); //ceshi2(); init(); dp(); //ceshi(); cout<

注：一开始没有注意到是多组输入，所以一直错。而且理论上好像应该用long long int比较保险，但是我看网上别人的代码int也过了。


另外的理解：

1.确定边界条件的时候，可以是画表格，然后看看当前格受哪些格的影响（即找到上一状态的格子）。然后那些上一状态在表格外的格子就是要单独确定的边界。

2.从理论角度来说，这个递推的循环ij谁在外面应该是无关影响的。但是对于思想的理解是不同的。有时候，在解完题后，调换内外循环重新考虑这个递推过程是会有新的理解。

对于本体，该递推关系式的两种理解方式：

（1）对于外层循环为k来说：一对一对得搬东西，先确定搬一对选在前i个里面最少的疲劳度为多少。然后算搬两对，搬三对····

（2）对于外层循环为n来说：一个一个得按顺序考虑这n个东西，如果只能选前2个搬，搬0-k对东西分别获得的疲劳度为多少，那要是能选3个了呢，4个呢····