分析题目以后得出,对于一个连续等差递增的序列,例如1,2,3,4,5,6,每次选择其中后一半,减去能减的最大数,则是最优操作。
上述序列经过一次操作后变为1,2,3,0,1,2,此时可抛弃后一半(已经能和前一半一起处理了),操作前三个数的后两个,以此类推,总共三次操作可把所有数减成0
分析得到递推式:设n为序列长度,ans(n)=ans(n/2)+1
于是代码变得很简单了:
#include<bits/stdc++.h>
using namespace std;
int a;
int r(int num){
return num==1? 1:r(num/2)+1;
}
int main(){
while(scanf("%d",&a)!=EOF){
printf("%d\n",r(a));
}
return 0;
}
UVa 11384 Help is needed for Dexter的更多相关文章
-
UVA.11384 Help is needed for Dexter (思维题)
UVA.11384 Help is needed for Dexter (思维题) 题意分析 同样水题一道,这回思路对了. 给出数字n,面对一个1,2,3,4--n的数字序列,你可以对他们的部分或者全 ...
-
UVA 11384 Help is needed for Dexter(问题转化 递归)
Help is needed for Dexter Time Limit: 3 Second Dexter is tired of Dee Dee. So he decided to keep Dee ...
-
UVa 11384 - Help is needed for Dexter 分析, 树状数组 难度: 0
题目 https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&a ...
-
UVa 11384 Help is needed for Dexter 正整数序列
给定一个正整数 n ,你的任务使用最少的操作次数把序列 1, 2, 3, -- , n 中的所有数都变成 0 .每次操作可以从序列中选择一个或者多个数,同时减去一个相同的正整数.比如,1, 2, 3 ...
-
UVa 11384 Help is needed for Dexter (递归)
题意:给定一个n表示1到n的序列,让你用最小的步数把这个序列都变为0,每个操作可以从序列中选择一个或多个个,同时减掉一个正整数,求最少的步数. 析:一看这个题,感觉挺高深的,但是静下心来想想,其实挺简 ...
-
UVA 11384 Help is needed for Dexter(递归)
题目链接:https://vjudge.net/problem/UVA-11384 这道题要分析得透: 如果我们手模的话,会发现:如果先将大于$\frac{n}{2}$的数都减去$\frac{n}{2 ...
-
【巧妙算法系列】【UVA 11384】 Help is needed for Dexter 正整数序列
Help is needed for Dexter Time Limit: 3 Second Dexter is tired of Dee Dee. So he decided to keep Dee ...
-
uva------Help is needed for Dexter(11384)
Problem H Help is needed for Dexter Time Limit: 3 Second Dexter is tired of Dee Dee. So he decided t ...
-
Help is needed for Dexter UVA - 11384(二分)
本来抱着wa一发的心态写写,没想到过了. 算是一种二分吧. 也就是说,减数取太大和太小都不好,怎样是最好的呢?当然是,每次减去一个数之后新形成的序列和前面的序一样是最好的 这样的话,本来想写个二分,但 ...
随机推荐
-
discuz上传图片提示附件文件无法保存
两个可能: 1. 服务器文件夹权限不足 discuz附件保存在./data/attachments下,data文件夹的属性要求必须为777 #cd到data的上一级目录然后执行: data 2. 附件 ...
-
UML2
UML中有3种构造块:事物.关系和图,事物是对模型中最具有代表性的成分的抽象:关系是把事物结合在一起:图聚集了相关的的事物.具体关系图标如下 说明:构件事物是名词,是模型的静态部分.行为事物是动态部分 ...
-
C#调用存储过程详解
连接字符串: string conn = ConfigurationManager.ConnectionStrings["NorthwindConnectionString"].C ...
- Duanxx 的 STM32 学习: 中断向量表操作
-
不用Root权限获取已经安装的Apk安装包
在安卓设备上安装的apk都会被保留一份在/data/app目录下,但是该目录对于普通用户来说只有可执行权限,是无法访问的. 但是其子文件具有可读权限. 意思也就说我们直接去查看/data/app这个目 ...
-
spring cloud 专题二(spring cloud 入门搭建 之 微服务搭建和注册)
一.前言 本文为spring cloud 微服务框架专题的第二篇,主要讲解如何快速搭建微服务以及如何注册. 本文理论不多,主要是傻瓜式的环境搭建,适合新手快速入门. 为了更好的懂得原理,大家可以下载& ...
-
java获取机器IP地址常用方法
private String getHostIP(){ Enumeration<NetworkInterface> allNetInterfaces = null; String resu ...
-
python实现文件的复制
# 练习: # 1. 写程序,实现文件的复制,(注:只复制文件,不复制文件夹) # 要求: # 1) 要考虑文件关闭的问题 # 2) 要考虑超大文件无法一下加载到内存的问题 # 3) 要能复制二进 ...
-
获取用户登陆所在的ip及获取所属信息
package com.tcl.topsale.download.entity; public class GeoLocation { private String countryCode; priv ...
-
idea 设置编译的编码方式
Settings->Build,Execution,Deployment->Compiler->Java Compiler,右边的详情列表中,Javac Options有设置参数的地 ...