# Tag-DP

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

2019-02-05 23:39:44 |  0 Comments  |  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

emmm……

nope！ 如果是a，b的范围是1 <= a,b <= 20000000000呢？你还暴力拆开检查么？你家计算机跑上一天都不一定能跑出来。

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;
}

long long solve(long long x){
long long ans = 0;
k = 0;
memset(m,0,sizeof(m

## Input

【提示】 1.输入文件可能很大，请采用快速的读入方式。
2.必然存在一种最优的买卖方案满足：

3 100
1 1 1
1 2 2
2 2 3

225.000

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct

YES
YES
YES
YES
YES
NO

·字符串长度不超过1 00000

· 1 <=n<=100

·通配符个数不超过10

## 题解

DP+Hash（刚学Hash）
f[i][j]表示第i个通配符能否匹配到第j个位置。

## 代码

#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[

Title - Artist
0:00