<USACO09JAN>气象测量/气象牛The Baric Bovineの思路

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

我..莫名其妙搞出来的

随便搞搞..幻想中的dp结果对了

我也很迷茫

Description

为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N <= 100)次气压测量并按顺序记录了结果M_1...M_N(1 <= M_i <= 1,000,000).
Betsy想找出一部分测量结果来总结整天的气压分布. 她想用K(1 <= K <= N)个数s_j(1 <= s_1 < s_2 < ... < s_K <= N)来概括所有测量结果. 她想限制如下的误差:对于任何测量结果子集,每一个非此子集中的结果都会产生误差.总误差是所有测量结果的误差之和.更明确第说, 对于每一个和所有s_j都不同的i:
* 如果 i 小于 s_1, 误差是:2 * | M_i - M_(s_1) |
* 如果i在s_j和s_(j+1)之间,误差是:| 2 * M_i - Sum(s_j, s_(j+1)) | 注:Sum(x, y) = M_x + M_y; (M_x 和 M_y 之和)
* 如果i大于s_K,误差为:2 * | M_i - M_(s_K) |
Besty给了最大允许的误差E (1 <= E <= 1,000,000),找出最小的一部分结果使得误差最多为E.

Input

第一行: 两个空格分离的数: N 和 E
第2..N+1行: 第i+1行包含一次测量记录:M_i

Output

第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目和使用那个测量数目能达到的最小误差

Sample Input

4 20

10
3

20
40

Sample Output

2 17

Hint

【样例说明】

选择第二和第四次测量结果能达到最小误差17. 第一次结果的误差是2*|10-3| = 14;第三次结果的误差是|2*20 - (3+40)|=3.

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 using namespace std;

 int n,e;

 long long m[],ero[][],dp[][];//ero选i和j产生的误差//dp以j结尾的时候，有i个最少测量数目 能达到的最小误差

 long long abss(long long a)

 {

     if(a<)return -a;

     return a;

 }

 int main()

 {

     int i,j,k;

     scanf("%d%d",&n,&e);

     for(i=;i<=n;i++)scanf("%lld",&m[i]);

     long long ans=n,anss=;

     for(k=;k<=n;k++)

     {

         for(i=k+;i<=n;i++)

             for(j=k+;j<=i-;j++) /*枚举题中的i*/ ero[k][i]+=abss(*m[j]-m[i]-m[k]);

         for(i=;i<k;i++) ero[k][]+=*abss(m[i]-m[k]); //取k时，小于k的i值产生的误差

         for(i=k+;i<=n;i++) ero[k][n+]+=*abss(m[i]-m[k]);// 取k时 大于k的i值产生的误差

     }//关于误差 

     for(i=;i<=n;i++)

     {

         dp[][i]=ero[i][]+ero[i][n+];

         if((dp[][i]<=e) && (dp[][i]<anss))

         {

             anss=dp[][i];ans=;

         }

     }//处理只取一个数的情况，也就是只取数i的情况 预处理 

     if(ans==){printf("%lld %lld\n",ans,anss);return ;}//如果可以只取一个数emm且满足条件啦 

     for(k=;k<=n;k++)//最少能达到误差小于等于E的测量数目

         for(i=k;i<=n;i++)//枚举结尾的数

         {

             dp[k][i]=;

             for(j=k-;j<i;j++)//枚举上一轮的结尾数

             {

                 long long err=ero[j][i]+ero[i][n+]-ero[j][n+]; //相比上一轮多的误差

                 dp[k][i]=min(dp[k][i],dp[k-][j]+err);

             }

             if((dp[k][i]<=e) && (dp[k][i]<anss) && (k<=ans)) anss=dp[k][i],ans=k;//找最优解emm

         }

     printf("%lld %lld\n",ans,anss);

 return ;

 }

点击查看丑陋の代码&注释

<USACO09JAN>气象测量/气象牛The Baric Bovineの思路的更多相关文章

[USACO09JAN] 气象测量/气象牛The Baric Bovine 解题报告(DP)
题目链接:https://www.luogu.org/problemnew/show/P2933 Description 为了研究农场的气候,Betsy帮助农夫John做了N(1 <= N &l ...

P2933 [USACO09JAN]气象测量The Baric Bovine
传送门挺显然的 $dp$ ,然鹅一开始想的是 $dfs$ 乱剪剪枝搞了 $70$ 分... 设 $f[i][j]$ 表示切了 $i$ 次,当前切的位置为 $j$ 的最小误差那么转移显然枚举上一个切 ...

中国气象网气象数据开放平台 API用法（Android）
因为要做个天气应用.须要找个天气的API.上网上搜了下都是那几个,并且基本都过时了.百度有个天气API,只是貌似仅仅能提供当天的.网上提到的中国气象接口的文章,大都用的时旧API,有的被封了,有的永远 ...

【bzoj1598】【 [Usaco2008 Mar]牛跑步】启发式搜索思路+spfa
(上不了p站我要死了,侵权度娘背锅) 最近复习搜索,先从启发式搜索来吧. 感觉启发式搜索这玩意挺玄学的,先从其思想入手,做一道经典的K短路. Description BESSIE准备用从牛棚跑到池塘的 ...

【随缘更(gu)】牛客D4简要思路（没有题解）
T1 当然不能枚举每个区间,于是我们考虑算贡献. 对于每个位置i,我们计算其作为区间内第一个出现ai的位置的区间总数,则有ans=sigma( i - last[i] ) * ( n - i + 1 ...

head first 设计模式笔记2-观察者模式：气象观测站
设计原则:为了交互对象之间的松耦合设计而努力. 1.设计模式的一些理解 1)知道OO基础,并不足以让你设计出良好的OO系统 2)良好的OO设计必须具备可复用.可扩充.可维护三个特性 3)模式可以让我们 ...

[置顶] 长谈：关于 View Measure 测量机制，让我一次把话说完
<倚天屠龙记中>有这么一处:张三丰示范自创的太极剑演示给张无忌看,然后问他记住招式没有.张无忌说记住了一半.张三丰又慢吞吞使了一遍,问他记住多少,张无忌说只记得几招了.张三丰最后又示范了一 ...

P2341 受欢迎的牛
受欢迎的牛洛谷链接题目大意: 有n头牛,牛会喜欢其他牛和自己,而喜欢是可以传递的,求被所有牛喜欢的牛的数量. 思路: 这是一道tarjan缩点的题目.被所有牛都喜欢的牛,一定会在一个强连通分量里. ...

Head First 设计模式之观察者模式（Observer Pattern）
前言: 这一节开始学习观察者模式,开始讲之前会先像第一节那样通过一个应用场景来引入该模式.具体场景为:气象站提供了一个WeatherData对象,该对象可以追踪获取天气的温度.气压.湿度信息,Weat ...

随机推荐

echars 柱状图点击事件
drawlineCRK() { let _this = this; ///绘制echarts 柱状图 let mycharts = this.$echarts.i ...

ios swift 判断uiviewcontroller时push present 进来的还是pop进来的
override func viewWillAppear(_ animated: Bool) { super.viewWillAppear(animated) //显示navbar self.navi ...

【转】 java类的加载和执行顺序
1.先执行Test类的静态代码块后执行Test类的main方法,说明要执行类的方法需要先加载这个类. 2.在创建ClassB的对象时,先去加载了父类ClassA.说明加载子类时如果没有加载父类,会先加 ...

<强化学习>开门帖
(本系列只用作本人笔记,如果看官是以新手开始学习RL,不建议看我写的笔记昂) 今天是2020年2月7日,开始二刷david silver ulc课程.https://www.youtube.com/w ...

协议（Protocol）
协议(Protocol)的基本概念协议的声明看起来比较类似于Java中一个类的接口,但是和接口不同的是:协议没有父类也不能定义实例变量. 协议是一种特殊的程序设计结构,用于声明专门被别的类实现的方法 ...

CodeForces 1006E Military Problem（DFS，树的选择性遍历）
http://codeforces.com/contest/1006/problem/E 题意: 就是给出n,m,共n个点[1,n],m次询问.第二行给出n-1个数a[i],2<=i<=n ...

JavaScript下判断元素是否存在
1. 判断表单元素是否存在(一) if("periodPerMonth" in document.theForm) { return true; } else{ return fa ...

Opencv笔记（五）——把鼠标当画笔
学习目标: 学习使用 OpenCV 处理鼠标事件学会使用函数cv2.setMouseCallback() 简单演示: 首先我们来创建一个鼠标事件回调函数,但鼠标事件发生是他就会被执 ...

hibernate中session.flush()
flush()session flush在commit之前默认都会执行, 也可以手动执行,他主要做了两件事: 1) 清理缓存. 2) 执行SQL. flush: Session 按照缓存中对象属性变化 ...

The website is API（1）
Requests 自动爬取HTML页面自动网路请求提交 robots 网络爬虫排除标准 Beautiful Soup 解析HTML页面实战 Re 正则表达式详解提取页面关键信息 Scrapy*框架 ...

正文

我..莫名其妙搞出来的

随便搞搞..幻想中的dp结果对了

我也很迷茫

Input

第一行: 两个空格分离的数: N 和 E
第2..N+1行: 第i+1行包含一次测量记录:M_i

Output

第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目和使用那个测量数目能达到的最小误差

Sample Input

4 20

Sample Output

2 17

Hint

【样例说明】

相关阅读

sap备份有什么用，sap client copy

仙帝归来下载，仙帝归来下载TXT八零

iis6.0配置thinkphp，配置iis7

ios内存小的赛车游戏，ios内存小的赛车游戏有哪些

linux打开连接的命令，linux 打开url命令

香港服务器经营性网站备案，香港服务器icp备案

平面拍摄有什么要求，平面拍摄有什么要求吗

4.5岁角色扮演游戏，角色扮演游戏适合多大宝宝

目录[+]

我..莫名其妙搞出来的

随便搞搞..幻想中的dp结果对了

我也很迷茫

Input 第一行: 两个空格分离的数: N 和 E 第2..N+1行: 第i+1行包含一次测量记录:M_i

Output 第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目 和 使用那个测量数目能达到的最小误差

Sample Input 4 20

Sample Output 2 17

Hint 【样例说明】

相关阅读

sap备份有什么用，sap client copy

仙帝归来下载，仙帝归来下载TXT八零

iis6.0配置thinkphp，配置iis7

ios内存小的赛车游戏，ios内存小的赛车游戏有哪些

linux打开连接的命令，linux 打开url命令

香港服务器经营性网站备案，香港服务器icp备案

平面拍摄有什么要求，平面拍摄有什么要求吗

4.5岁角色扮演游戏，角色扮演游戏适合多大宝宝

目录[+]

Input

第一行: 两个空格分离的数: N 和 E
第2..N+1行: 第i+1行包含一次测量记录:M_i

Output

第一行: 两个空格分开的数: 最少能达到误差小于等于E的测量数目和使用那个测量数目能达到的最小误差

Sample Input

4 20

Sample Output

2 17

Hint

【样例说明】