Tag-DP

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2019-02-05 23:39:44 |  0 Comments  |  DP

BUPT校内训练&Codeforces 623B 序列DP

Description

You are given array ai of length n. You may consecutively apply two operations to this array:
·remove some subsegment (continuous subsequence) of length m < n and pay for it m·a coins;
·change some elements of the array by at most 1, and pay b coins for each change.
Please note that each of operations may be applied at most once (and may be not applied at all) so you can remove only one segment and each number may be changed (increased or decreased) by at most 1. Also note, that you are not allowed to delete the whole array.
Your goal is to calculate the minimum number of coins that you need to spend in order to make the greatest common divisor of the elements of the resulting array be greater than 1.

Input

The first line of the input contains integers n, a and b (1 ≤ n ≤ 1 000 000, 0 ≤ a, b ≤ 109) — the length of the array, the cost of removing a single element in the first operation and the cost of changing an element, respectively.
The second line contains n integers ai (2 ≤ a_i

 2019-01-27 22:31:09 |  0 Comments  |  DP

数位DP & BZOJ1026[SCOI 2009]windy数题解

数位DP

这个鬼东西是个啥????我咋没见过呢?
emmm……
数位DP,顾名思义,利用数字的每一个数位(个、十、百、千、万、……)来计算的动态规划算法。
啥?我还是不懂的?
那么我们还是来说一下这种算法的适用题型吧……
给定两个数a,b,求满足给定条件的数的个数。(举个栗子:求ab之间不包含子串“62”的数的个数)
这也太明显了吧……按照一个个把数字拆开检查不就行了么……
nope! 如果是a,b的范围是1 <= a,b <= 200000000001<=a,b<=20000000000呢?你还暴力拆开检查么?你家计算机跑上一天都不一定能跑出来。
那咋整?
数位DP!
数位DP的基本思路就是按照数位对数字进行拆开,但是数位DP会利用每一位的数进行动态规划从而达到消除重复计算的作用,从而减小时间复杂度。像是上面的例子,我们可以想象,其实我们计算很多数的时候是在进行一些不必要的重复计算的。而数位DP就是为了这类问题避开这些重复计算而被总结设计出来的。
下面我们来说一下数位DP的核心步骤。
枚举当前是第几位,然后枚举这一位上的数,再枚举这个的低一位的数,检查是否满足条件,进行状态转移。这一步的伪代码如下

void init(){
    memset(dp,0,sizeof(dp));
    for(int i = 0;i <= 9;++i)
        dp[1][i] = 1;
    for(int i = 2;i <= 10;++i)
        for(int j = 0;j <= 9;++j)
            for(int k = 0;k <= 9;++k){
                if(满足题目条件)
                    dp[i][j] += dp[i-1][k];
            }
    return;
}

对数位DP数组计算完成后,对于题中的a,b,我们就只需要计算0——b中满足题目条件的数的个数和0——a-1中满足题目条件的个数,然后相减就可以得到我们想要的结果了。(差分前缀和的思想)一般来说这一步的代码是比较固定的,大致如下,具体题目自己调整。

long long solve(long long x){
    long long ans = 0;
    k = 0;
    memset(m,0,sizeof(m
 2017-01-18 09:08:42 |  0 Comments  |  CDQ分治 DP

NOI2007 货币兑换 Cash 【CDQ分治 斜率优化DP】

Description

小Y最近在一家金券交易所工作。该金券交易所只发行交易两种金券:A纪念券(以下简称A券)和 B纪念券(以下简称B券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 K 天中 A券 和 B券 的价值分别为 AK 和 BK(元/单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。比例交易法分为两个方面:(a)卖出金券:顾客提供一个[0,100] 内的实数 OP 作为卖出比例,其意义为:将 OP% 的 A券和 OP% 的 B券 以当时的价值兑换为人民币;(b)买入金券:顾客支付 IP 元人民币,交易所将会兑换给用户总价值为 IP 的金券,并且,满足提供给顾客的A券和B券的比例在第 K 天恰好为 RateK;例如,假定接下来 3 天内的 Ak、Bk、RateK 的变化分别为:

假定在第一天时,用户手中有 100元 人民币但是没有任何金券。用户可以执行以下的操作:

注意到,同一天内可以进行多次操作。小Y是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来N天内的A券和B券的价值以及Rate。他还希望能够计算出来,如果开始时拥有S元钱,那么N天后最多能够获得多少元钱。

Input

输入第一行两个正整数N、S,分别表示小Y能预知的天数以及初始时拥有的钱数。接下来N行,第K行三个实数AK、BK、RateK,意义如题目中所述。对于100%的测试数据,满足:0<AK≤10;0<BK≤10;0<RateK≤100;MaxProfit≤109。
【提示】 1.输入文件可能很大,请采用快速的读入方式。
2.必然存在一种最优的买卖方案满足:
每次买进操作使用完所有的人民币;
每次卖出操作卖出所有的金券

Output

只有一个实数MaxProfit,表示第N天的操作结束时能够获得的最大的金钱数目。答案保留3位小数

Sample Input

3 100
1 1 1
1 2 2
2 2 3

Sample Output

225.000

HINT

题解:
感谢hzwer的代码,初学CDQ分治,还是个菜鸡。
 2017-01-08 11:52:59 |  0 Comments  |  hash DP

【BZOJ3507【CQOI】通配符匹配DP+Hash

题目描述

几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个,一个是星号(“*”),可以匹配0个及以上的任意字符:另一个是问号(“?”),可以匹配恰好一个任意字符。
现在需要你编写一个程序,对于给定的文件名列表和一个包含通配符的字符串,判断哪些文件可以被匹配。

输入格式

第一行是一个由小写字母和上述通配符组成的字符串。
第二行包含一个整数n,表示文件个数。
接下来n行,每行为一个仅包含小写字母字符串,表示文件名列表。

输出格式

输出n行,每行为“YES”或“NO”,表示对应文件能否被通配符匹配。

样例输入

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

样例输出

YES
YES
YES
YES
YES
NO

数据范围及提示

对于100%的数据

·字符串长度不超过1 00000

· 1 <=n<=100

·通配符个数不超过10

题解

DP+Hash(刚学Hash)
f[i][j]表示第i个通配符能否匹配到第j个位置。
因为一个*会把字符串分成两段,所以这个*分开的两边一定是要求一样的,这里可以利用hash判断。
然后我们就可以得到通配符串被*分成好几段,这样就可以得到转移。
枚举起点,如果可以匹配就可以转移。
有一些比较方便的处理,比如S最后加一个?,以及s最后加任意一个字符
这样的时间复杂度封顶大概是O(N*k*len),所以一开始自己想到了但是没敢写,但是发现这个转移其实时间复杂度是不满的,所以可以AC
%%%DaD3zZ

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int maxn = 100010;
const int base = 131;
char S[maxn],s[maxn];
ull hash[2][maxn],bin[maxn];
int p[20],t,n;
bool f[12][maxn];
inline void hash_table(char str[
 2016-12-11 21:25:50 |  1 Comments  |  DP 最短路

[NOIP2016Day1T3]换教室classroom

[NOIP2016Day1T3]换教室classroom

题目描述

对于刚上大学的牛牛来说, 他面临的第一个问题是如何根据实际情况中情合适的课程。
在可以选择的课程中,有2n节课程安排在n个时间段上。在第 i ( 1≤ i≤n)个时同段上, 两节内容相同的课程同时在不同的地点进行, 其中, 牛牛预先被安排在教室 ci上课, 而另一节课程在教室 di进行。
在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的n节安排好的课程。如果学生想更换第i节课程的教室,则需要提出中情。若申请通过,学生就可以在第 i个时间段去教室 di上课, 否则仍然在教室 ci上课。
由于更换教室的需求太多, 申请不一定能获得通过。 通过计算, 牛牛发现申请更换第 i节课程的教室时, 中情被通过的概率是一个已知的实数 ki, 并且对于不同课程的申请, 被通过的概率是互相独立的。
学校规定, 所有的申请只能在学期开始前一次性提交, 并且每个人只能选择至多m节课程进行申请。 这意味着牛牛必须一次性决定是否申请更换每节课的教室, 而不能根据某些课程的申请结果来决定其他课程是否申请; 牛牛可以申请白己最希望更换教室的 m门课程,也可以不用完这m个中情的机会,甚至可以一门课程都不申请。
因为不同的课程可能会被安排在不同的教室进行, 所以牛牛需要利用课问时间从一间教室赶到另一间教室。
牛牛所在的大学有 v个教室,有 e条道路。每条道路连接两间教室, 并且是可以双向通行的。 由于道路的长度和拥;i者程度不同, 通过不同的道路耗费的体力可能会有所不同。当第i ( 1≤i≤n-1 )节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一节课的教室。
现在牛牛想知道,申请哪几门课程可以使他因在教室问移动耗费的体力值的总和的期望值最小,请你帮他求出这个最小值。

输入格式

第一行四个整数 n,m,v,e 。 n表示这个学期内的时间段的数量; m表示牛牛最多可以申请更换多少节课程的教室; v表示牛牛学校里教室的数量; e表示牛牛的学校里道路的数量。
第二行n个正整数,第 i ( 1≤ i≤ n)个正整数表示c,,即第 i个时间段牛牛被安

Title - Artist
0:00