Pollywog CodeForces - 917C (状压)

时间：2022-09-16 23:59:39

链接

大意: 一共n个格子, 初始$x$只蝌蚪在前$x$个格子, 每次最左侧的蝌蚪向前跳, 跳跃距离在范围[1,k], 并且每只蝌蚪跳跃都有一定花费, 有$q$个格子上有石头, 若有蝌蚪跳到某块石头上, 会有产生一定花费, 可能为负, 求移动到最右侧的最小花费

刚开始想暴力状压的话状态是$2^8$, 在矩乘的话要达到$2^16logn$, 显然不能接受

看了题解发现因为每次只有最左侧蝌蚪跳, 所以蝌蚪一定一直都在连续的k个格子上, 状态数是$\binom {k}{x}$

这样的话状态数最大是$\binom {8}{4}=70$, 复杂度可以接受

Pollywog CodeForces - 917C (状压)的更多相关文章

  1. CodeForces 11D(状压DP 求图中环的个数)

    Given a simple graph, output the number of simple cycles in it. A simple cycle is a cycle with no re ...

  2. Vladik and cards CodeForces - 743E (状压)

    大意: 给定序列, 求选出一个最长的子序列, 使得任选两个[1,8]的数字, 在子序列中的出现次数差不超过1, 且子序列中相同数字连续. 正解是状压dp, 先二分转为判断[1,8]出现次数>=x ...

  3. Clear The Matrix CodeForces - 903F (状压)

    大意: 给定4行的棋盘以及4种大小的正方形方块, 每种各有一定花费, 每次可以选一种方块放在棋盘上, 棋盘对应格子全变为'.', 求最少花费使得棋盘全部变成'.' 状压基本操作练习, 状态取12位, ...

  4. Codeforces 678E 状压DP

    题意:有n位选手,已知n位选手之间两两获胜的概率,问主角(第一个选手)最终站在擂台上的概率是多少? 思路:一看数据范围肯定是状压DP,不过虽然是概率DP,但是需要倒着推:我们如果正着推式子的话,初始状 ...

  5. Codeforces 8C 状压DP

    题意:有个人想收拾行李,而n个物品散落在房间的各个角落里(n < 24).现在给你旅行箱的坐标(人初始在旅行箱处),以及n个物品的坐标,你一次只能拿最多两个物品,并且拿了物品就必须放回旅行箱,不 ...

  6. Keyboard Purchase CodeForces - 1238E &lpar;状压&rpar;

    大意: 给定串$s$, 字符集为字母表前$m$个字符, 求一个$m$排列$pos$, 使得$\sum\limits_{i=2}^n|{pos}_{s_{i-1}}-{pos}_{s_{i}}|$最小. ...

  7. Codeforces 1215E 状压DP

    题意:给你一个序列,你可以交换序列中的相邻的两个元素,问最少需要交换多少次可以让这个序列变成若干个极大的颜色相同的子段. 思路:由于题目中的颜色种类很少,考虑状压DP.设dp[mask]为把mask为 ...

  8. codeforces 1185G1 状压dp

    codeforces 1185G1. Playlist for Polycarp (easy version)(动态规划) 传送门:https://codeforces.com/contest/118 ...

  9. Crisp String CodeForces - 1117F &lpar;状压&rpar;

    #include <iostream> #include <algorithm> #include <cstdio> #include <math.h> ...

随机推荐

  1. 使用python的Flask实现一个RESTful API服务器端&lbrack;翻译&rsqb;

    最近这些年,REST已经成为web services和APIs的标准架构,很多APP的架构基本上是使用RESTful的形式了. 本文将会使用python的Flask框架轻松实现一个RESTful的服务 ...

  2. 【转】windows环境下安装win8&period;1&plus;Mac OS X 10&period;10双系统教程

    先要感谢远景论坛里的各位大神们的帖子  没有他们的分享我也不能顺利的装上Mac OS X 10.10! 写这篇随笔主要是为了防止自己遗忘,同时给大家分享下我的经验. 本教程适用于BIOS+MBR分区的 ...

  3. Android Studio 导入百度地图jar和so的正确方式

    //这部分内容在百度地图的官方文档中写的比较模糊 //感觉在这种事情上浪费实际很不好,遂记录如下 //以下仅是方法之一 step1 下载sdk后解压,并把libs中的全部内容拷贝到app/libs目录 ...

  4. elk平台搭建

    很多时候我们需要对日志做一个集中式的处理,但是通常情况下这些日志都分布到n台机器上面,导致一个结果就是效率比较低,而ELK平台可以帮助我们解决这么一件事情: ELK下载:https://www.ela ...

  5. 移动端前端笔记 — 遇到的常见JS与CSS问题及解决方法 （ 摘自zdwzdwzdw）

    笔者接触移动前端快一年了,特将平时的一些笔记整理出来,希望能够给需要的人一些小小的帮助.同时也由于笔者的水平有限,虽说都是笔者遇到过使用过的,但文中可能也会出现一些问题或不严谨的地方,望各位指出,不胜 ...

  6. ASP&period;NET MVC3入门教程之环境搭建

    本文转载自:http://www.youarebug.com/forum.php?mod=viewthread&tid=90&extra=page%3D1 什么是ASP.NET MVC ...

  7. hihocoder 1061&period;Beautiful String

    题目链接:http://hihocoder.com/problemset/problem/1061 题目意思:给出一个不超过10MB长度的字符串,判断是否里面含有一个beautiful strings ...

  8. 基于visual Studio2013解决C语言竞赛题之1032平方和

          题目 解决代码及点评 /* 编程序将一个正整数写成其它两个正整数的平方和,若不能成立时输出"NO".例如 5 ＝ 1^2 + 2^2 , 25 ...

  9. Handlebars 和 angularjs 之间的区别

    handlebarsjs算不上框架,只是一种js模板引擎,是模板库,模板库的主要作用是:你想要生成某一大片有一定规律的界面,比如商品详情,不同商品之间差的只是名称,价格,图片,介绍这些,但是结构一样的 ...

  10. sql中的等于和不等于， &&num;39&semi;&equals;&&num;39&semi; &comma;&&num;39&semi;&excl;&equals;&&num;39&semi;&comma;&&num;39&semi;&lt&semi;&gt&semi;&&num;39&semi;&comma;&&num;39&semi;is null&&num;39&semi;&period;&period;&period;&period;

    不等于:<> ,!=,~= ,^= 这四个符号据说都可以在oracle中表示不等于,但是试了之后发现<> ,!= ,^=是可以的,~=不行,需要注意的是,只有<>是 ...

相关文章