rqnoj-225-书本整理-逆向思维dp

本文主要是介绍rqnoj-225-书本整理-逆向思维dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

逆向思维。

题目要求拿走k本书，那么就求从中拿n-k本书。

dp[i][j]:代表拿第i本书，从前i中拿k本书，最小的整齐度。

num[i]： 第i本书的高度。

dp[i][j]=dp[0...i-1][j-1]+|num[i]-num[j]|;

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define INF 9999999
struct list
{int x;int y;
}node[1001];
int cmp(struct list a,struct list b)
{return a.x<b.x;
}
int num[101];
int dp[101][101];
int main()
{int n,k,i,j,kk;while(scanf("%d%d",&n,&k)!=EOF){k=n-k;for(i=0;i<n;i++)scanf("%d%d",&node[i].x,&node[i].y);sort(node,node+n,cmp);for(i=0;i<n;i++)num[i]=node[i].y;for(i=0;i<n;i++){dp[i][1]=dp[i][0]=0;for(j=2;j<n;j++)dp[i][j]=INF;}for(i=0;i<n;i++){for(j=2;j<=k;j++){for(kk=0;kk<i;kk++){dp[i][j]=min(dp[kk][j-1]+(int)fabs(num[i]-num[kk]),dp[i][j]);}}}int minn;minn=INF;for(i=0;i<n;i++){minn=min(minn,dp[i][k]);}cout<<minn<<endl;}return 0;
}

这篇关于rqnoj-225-书本整理-逆向思维dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---