题解 P1103 【书本整理】
zhaimingshuzms
2017-06-02 17:41:35
#这题可以滚起来
楼下的代码没有滚动的，我就写个滚动的，采用从n本书中选n-k本这种动归方式（显然这样更好思考）。滚动的好处就是更好理解（真的吗），初始化更简单，空间更小（好像没什么用），总之比不滚动好；
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=101,P=1e9;//P是某个大数
pair<int,int>a[N];//捆绑在一起，sort时就不用写cmp了
int n,k,ans=P,f[N];
int main()
{
scanf("%d%d",&n,&k);
for (int i=1; i<=n; i++) scanf("%d%d",&a[i].first,&a[i].second);
sort(a+1,a+n+1);
for (int j=2; j<=n-k; j++)//i——考虑第i个；j——选了j个
for (int i=n; i>=j; i--)//滚动时i要倒着扫，才能参考j-1行的表格，因为l总是小于i
{
f[i]=P;
for (int l=j-1; l<=i-1; l++)
f[i]=min(f[l]+abs(a[i].second-a[l].second),f[i]);
}
for (int i=n-k; i<=n; i++) ans=min(ans,f[i]);//i从n-k开始扫，之前的由于不到需选书的数目，不可能是答案
printf("%d",ans);
return 0;
}
```