MyException - 我的异常网
当前位置:我的异常网» 编程 » 【Coder Force】#360B - Levko and Array(DP 2分枚

【Coder Force】#360B - Levko and Array(DP 2分枚举)

www.MyException.Cn  网友分享于:2015-02-11  浏览:0次
【Coder Force】#360B - Levko and Array(DP 二分枚举)

题目大题:CF上的题目还是比较容易读懂的。这道题的意思嘛,他是说,有一个不超过2000个数的数组,每一个数与后面的数的绝对值称为value,那么所有当中最大的value就是整个数组的value,现在你有k次变换,每一次可以将其中的一个数变为任何一个使得数组价值最小的数。
假如题目的价值是所有的之和,也可以用这道题的方法。
思路:
dp[i]表示的是到i这个位置,使得数组符合条件的最少变换次数。
这个符合条件就奇妙了,这个符合条件是由你定的,最终的符合条件就是答案。
简单来说:你举例一个答案,放进去,看看能不能使得整个数组的变换次数小于等于给定的K次,假如可以的话,那么这个数存起来。
接下来我们尝试更大一点可以不可以呢?可以的话重复以上操作,不可以的话就是之前的数拉。
我们枚举的范围是0-2e9,这么大的范围,傻眼了,不急,二分搜索是一个不错的方法。
好了,方法说完了。接下来是考验你DP功底的时候了,可惜这边我差劲的很,没办法给大家切入点和突破性的建议和见解了。
只能给大家讲一下这个模型,放心,等我学成之后我定给大家剖析每一道我A的题。
dp[i]=min(dp[i],dp[j]+i-j-1)(1

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int dp[2010];
int a[2010];
const int inf = 2e9;
int n, m;

bool  bs(long long mid)
{
    for (int i = 1; i <= n; i++)
    {
        dp[i] = i - 1;
        for (int j = 1; j < i; j++)
        if (abs(a[i] - a[j]) <= (i - j)*mid)
            dp[i] = min(dp[i], dp[j] + (i - j - 1));
        if (dp[i] + n - i <= m)return true;
    }
    return false;
}
int main()
{
    while (cin >> n >> m)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        long long l = 0, r = inf;
        int ans = 0;
        while (l <=r)
        {
            long long mid = (l + r) >> 1;//int+int会超过int的范围,导致爆掉了。= =
            if (bs(mid))
            {
                ans = mid; r = mid - 1;
            }
            else l = mid + 1;
        }
        cout << ans << endl;
    }
}

文章评论

科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
初级 vs 高级伟德国际app者 哪个性价比更高?
初级 vs 高级伟德国际app者 哪个性价比更高?
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
为什么程序员都是夜猫子
为什么程序员都是夜猫子
编程语言是女人
编程语言是女人
程序员必看的十大电影
程序员必看的十大电影
中美印日四国程序员比较
中美印日四国程序员比较
Web伟德国际app人员为什么越来越懒了?
Web伟德国际app人员为什么越来越懒了?
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
Java程序员必看电影
Java程序员必看电影
老程序员的下场
老程序员的下场
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
一个程序员的时间管理
一个程序员的时间管理
Web伟德国际app者需具备的8个好习惯
Web伟德国际app者需具备的8个好习惯
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
程序员的鄙视链
程序员的鄙视链
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
漫画:程序员的工作
漫画:程序员的工作
2013年美国伟德国际app者薪资调查报告
2013年美国伟德国际app者薪资调查报告
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
那些争议最大的编程观点
那些争议最大的编程观点
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
 程序员的样子
程序员的样子
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
代码女神横空出世
代码女神横空出世
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
每天工作4小时的程序员
每天工作4小时的程序员
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
60个伟德国际app者不容错过的免费资源库
60个伟德国际app者不容错过的免费资源库
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员和编码员之间的区别
程序员和编码员之间的区别
总结2014中国互联网十大段子
总结2014中国互联网十大段子
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
10个调试和排错的小建议
10个调试和排错的小建议
旅行,写作,编程
旅行,写作,编程
我是如何打败拖延症的
我是如何打败拖延症的
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
如何成为一名黑客
如何成为一名黑客
软件伟德国际app程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有