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

2023-10-16 20:48

本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/220695

相关文章

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Spring Boot 常用注解整理(最全收藏版)

《SpringBoot常用注解整理(最全收藏版)》本文系统整理了常用的Spring/SpringBoot注解,按照功能分类进行介绍,每个注解都会涵盖其含义、提供来源、应用场景以及代码示例,帮助开发... 目录Spring & Spring Boot 常用注解整理一、Spring Boot 核心注解二、Spr

MyBatisX逆向工程的实现示例

《MyBatisX逆向工程的实现示例》本文主要介绍了MyBatisX逆向工程的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学... 目录逆向工程准备好数据库、表安装MyBATisX插件项目连接数据库引入依赖pom.XML生成实体类、

Mysql中深分页的五种常用方法整理

《Mysql中深分页的五种常用方法整理》在数据量非常大的情况下,深分页查询则变得很常见,这篇文章为大家整理了5个常用的方法,文中的示例代码讲解详细,大家可以根据自己的需求进行选择... 目录方案一:延迟关联 (Deferred Join)方案二:有序唯一键分页 (Cursor-based Paginatio

Mysql中InnoDB与MyISAM索引差异详解(最新整理)

《Mysql中InnoDB与MyISAM索引差异详解(最新整理)》InnoDB和MyISAM在索引实现和特性上有差异,包括聚集索引、非聚集索引、事务支持、并发控制、覆盖索引、主键约束、外键支持和物理存... 目录1. 索引类型与数据存储方式InnoDBMyISAM2. 事务与并发控制InnoDBMyISAM

StarRocks索引详解(最新整理)

《StarRocks索引详解(最新整理)》StarRocks支持多种索引类型,包括主键索引、前缀索引、Bitmap索引和Bloomfilter索引,这些索引类型适用于不同场景,如唯一性约束、减少索引空... 目录1. 主键索引(Primary Key Index)2. 前缀索引(Prefix Index /

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b