裸裸的区间DP。

我们定义f[l][r] 为卖掉l到r之间的临时得到的最大收益。

n[x]为第x个物品的价值。

Cl为第几天出售

转移方程就应该是f[l][r]=max(f[l+1][r]+cl*n[l],f[l][r+1]+cl*n[r]);

最后附上代码）

题目要求最大，观察数据范围，结合经验，考虑贪心。

当我们现在的烤鸡翅数量大于需求时，直接卖出。

否则，寻找前面已经卖出的最大的数量，如果该数大于当前需求，则用当前数目替代该数。

正确性不难证明：根据这个方法，我们遍历到第 $i$ 个人时，已经保证在不影响卖出人数的情况下让卖出的鸡翅数量最少。

再往后遍历时，也仍然可以保证。

这样，就实现了局部最优解向整体最优解的转变。

这个过程可以用大根堆实现。

子任务1：测试点$1\sim 3$

$1\leq k\leq n\leq15$，显然可以使用搜索法。

枚举所有括号序列，判断其是否合法。

  1、连续的*不能超过k个。

  2、括号要匹配。

  3、SAS类型是非法括号序列。

时间复杂度O($N\times 3^N$),预计得分15分。

ps:可直接跳到子任务4。

子任务2：测试点$1\sim 13$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由S序列转移得到，因此需要定义额外的状态，定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

那么对于(),(S),(A),(SA),(AS)型，显然有：

 $d(l,r)=1$, ()型

 $d(l,r)+=1$, (S)型,$s(l+1,r-1)=1$

 $d(l,r)+=d(l+1,r-1)$, (A)型

 $d(l,r)+=d(l+tk+1,r-1)$, (SA)型,$1\leq tk\leq k,s(l+1,l+tk)=1$

 $d(l,r)+=d(l+1,r-tk-1)$, (AS)型,$1\leq tk\leq k,s(r-tk,r-1)=1$

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

 $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=d(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。因此，状态转移方程需要做出如下修改：

 $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

 $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

 $d(l,r)+=a(l,j)*d(j+tk+1,r)$, (ASA)型,$1\leq tk\leq k,s(j+1,j+tk)=1$

综上，算法的流程如下：

 1、预处理得出所有的$s(l,r)$。

 2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r)$。

 3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^4$)，预计得分65分。

子任务3：测试点$1\sim 15$

对于测试点$14\sim 15$,字符串中仅含？。那么状态$d(l_1,r_1+k)$和$d(l_2,r_2+k)$虽然表示的区间不同，但是结果必然是相同的。

因此，定义状态$f(i)$表示$i$个？构成的合法的序列的方案数。那么，状态转移方程修改为：

$f(1)=0$,一个?

$f(2)=1$,()型

$f(i)+=1$,(S)型

$f(i)+=f(i-2)$,(A)型

$f(i)=f(i-2-tk)$,(AS),(SA)型,$1\leq tk\leq k$

$f(i)=f(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=f(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

同样，也需要考虑重复计数的问题，定义$g(i)$表示单独的A类型的方案数。

那么状态转移方程需要做出部分修改：

$g(i)=f(i)$,()(S)(A)(SA)(AS)型

$f(i)=g(j)*f(i-j)$,AA型，$2\leq j\leq i - 2$

$f(i)=g(j)*f(i-j-tk)$,ASA型，$2\leq j\leq i-2,1\leq tk\leq k$

时间复杂度：O($N^3$),预计得分75分。

子任务4：测试点$1\sim 20$

显然是一道区间DP问题。

首先明确，合法的括号序列应该是(),(S),(A),(SA),(AS),AA,ASA。

定义$d(l,r)$表示区间$[l,r]$的子串是合法括号序列的方案数。通过观察可以发现，$d(l,r)$可以由非法括号序列转移得到，因此需要定义额外的状态。

  定义$s(l,r)$表示区间$[l,r]$能否构成合法的S型。

  定义$sa(l,r)$表示区间$[l,r]$的子串是SA型的方案数。

  定义$as(l,r)$表示区间$[l,r]$的子串是AS型的方案数。

那么对于(),(S),(A),(SA),(AS)型，显然有：

  $d(l,r)=1$, ()型

  $d(l,r)+=s(l+1,r-1)$, (S)型

  $d(l,r)+=d(l+1,r-1)$, (A)型

  $d(l,r)+=sa(l+1,r-1)$, (SA)型

  $d(l,r)+=as(l+1,r-1)$, (AS)型

对于AA、ASA型，需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $d(l,r)+=d(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=d(l,j)*sa(j+1,r)$, (ASA)型

同时需要维护AS,SA型，同样需要枚举中间的分隔点$j(l\leq j\leq r)$：

  $as(l,r)+=d(l,j)*s(j+1,r)$, (AS)型

  $sa(l,r)+=s(l,j)*d(j+1,r)$, (SA)型

但是，对于部分括号序列，会出现重复计数，例如()()()会被识别成A|AA或者AA|A，()*()*()会被识别成AS|ASA或ASA|S|A。

为了避免重复计数，要求在合并时只能合并一次，因此定义状态$a(l,r)$表示单独的A类型，也即(),(S),(A),(SA),(AS)型，这些类型的特点是不能拆分。

因此，状态转移方程需要做出如下修改：

  $a(l,r)=d(l,r)$,(),(S),(A),(SA),(AS)型

对于AA,ASA型，这是出现重复计数的类型：

  $d(l,r)+=a(l,j)*d(j+1,r)$, (AA)型

  $d(l,r)+=a(l,j)*sa(j+1,r)$, (ASA)型

综上，算法的流程如下：

  1、预处理得出所有的$s(l,r)$。

  2、从小到大依次枚举每个区间$[l,r]$，求出相应的$d(l,r),a(l,r),sa(l,r),sa(l,r)$。

  3、最终的答案即为$d(1,n)$。

注意：在运算过程中需要不断对$10^9+7$取余。

注意：通过观察可以得出，首字符必是(，尾字符必是)，可以进行特殊处理。

时间复杂度O($N^3$)，预计得分100分。

前置芝士：CDQ分治（当然不会也无所谓，我会尽量讲明白的ヾ(◍°∇°◍)ﾉﾞ）

看别人代码都是花里胡哨的线段树，树状数组，还有丧心病狂的平衡树。

好像没几个用 CDQ分治 写的

这道题本质上就是 CDQ分治（或者说二维偏序） 的模板题

将题目最开始的输入 $a_i$ 看做是对第 $i$ 个位置上增加了 $a_i$

查询操作根据前缀和，将询问拆成 $s-1,t$ 两个查询操作

第一个记录为-，第二个为+

题目中有两个维度：时间T 和 位置x

对于两个操作：修改操作 $i$,查询操作 $j$,当且仅当 $T_i \le T_j$ 并且 $x_i \le x_j$ 时，$i$ 对 $j$有影响

（之前这个地方有疑惑，现在大概明白了，这样是正确的，感谢赵老师解答）

时间T 已经默认排好序了，就剩 位置x 需要处理一下了，并且要求处理的过程中不能破坏 时间T 的顺序性

CDQ分治 闪亮登场

它的操作主要由本篇代码中的 solve 函数完成

solve(l,r) 分为三步：

solve(l,mid)  solve(mid+1,r) 以及处理 $[l,mid]$ 对 $[mid+1,r]$ 的影响

要注意的是，这里的处理必须比较容易进行（比如加法，减法，取min，取max等）

这个算法的正确性在蓝书上和网上都有证明，此处略。

对我而言，CDQ分治 最难的其实是理解

以这个题目为例，我们要计算的是满足 $T_i \le T_j$ 并且 $x_i \le x_j$ 的二元组 (i,j) 产生的影响。

正如上面所言，时间T 不能被打乱，还要计算 $x_i \le x_j$

而 CDQ分治 处理这个问题的方法，大多可以在证明中理解。

$\forall k \in [mid+1,r]$，$[mid+1,k-1]$ 这一段产生的影响已经在递归中计算过了。

主要看的就是 $[l,mid]$ 这一段。

可以发现，不管 $[l,mid]$ 这一段怎样交换，改变，这里面的元素在现在的 solve(l,r) 中始终处于 $[l,mid]$ 这一段。

而这意味着什么呢？

也许 $[l,mid]$ 这一段的内部 时间T 是混乱的，但是并不影响这一段中任何一个操作对 $[mid+1,r]$ 的影响！！！

那么，我们可以在 solve 函数结束，各种乱七八糟的影响计算完毕后，把 $[l,r]$ 中的操作序列调整成我们想要的样子。

比如在这个题目里，solve 函数中，我们按照归并排序的方式，将 $[l,mid]$ 和 $[mid+1,r]$ 以 $x$ 为关键字排序

（这里有点像归并排序求逆序对，结合代码理解，或者先去看看这道题）

然后就不难理解了叭(*^▽^*)

//CDQ分治第一弹[
//STO CDQ 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
const int maxn = 5e5 + 5;
struct query {
	int op,id,x,y;//id:若当前操作为询问，则为询问的编号
	//op:1为修改，2为负查询，3为正查询
	//x,y:操作的点和要增加的量 
	query() {
		op = id = x = y = 0;
	}
	query(int op,int id,int x,int y):op(op),id(id),x(x),y(y){}
}Q[maxn],b[maxn];//b数组：辅助进行归并排序 
int n,m,cnt,tot,ans[maxn];
int read() {
	int s = 0,f = 1;
	char c = getchar();
	for(;!isdigit(c);c = getchar()) {
		if(c == '-')f = -1;
	}
	for(;isdigit(c);c = getchar())s = (s << 1) + (s << 3) + (c ^ '0');
	return s * f;
}
void write(int x) {
	if(x > 9)write(x / 10);
	putchar(x % 10 + '0');
	return ;
}
void print(int x) {
	write(x);
	putchar('\n');
	return ;
}//快读快写 
//个人对于CDQ分治的理解：
//主要是解决偏序问题，当然这些偏序不都是裸的类似逆序对这样的
//对于答案的修改可能更加繁琐一点
//但是核心思想都是用CDQ分治解决偏序
//1：solve(l,mid)，2：solve(mid+1,r)和3：(l,mid)对(mid+1,r)的影响这三块
//需要根据题目的要求自行决定顺序
//不恰当的栗子：DP
//DP时后半部分的计算直接由前半部分的影响决定
//这时就要1,3,2这样处理
//而对于本题，处理需要两个区间都有序，所以要先递归 ，即1,2,3 
void solve(int l,int r) {
	if(l >= r)return ;
	int mid = l + r >> 1;
	solve(l , mid);
	solve(mid + 1 , r);
	//此处先递归是因为CDQ分治解决偏序类似归并排序
	//需要两个区间都是有序的才能进行进一步的处理
	int i = l,j = mid + 1,sum = 0;//Mergesort part
	//sum用来统计[l,mid]的修改对[mid + 1,r]的影响 
	for(int k = l;k <= r;++ k) {
		if(j > r||(i <= mid&&Q[i].x <= Q[j].x)) {
			//此时当前的i对于[j,r]区间都有影响
			//记录在sum里，当查找到一个i，使得i无法对于j产生影响
			//那么再统计前面所有的i对当前j的影响
			//写的不太明白，可以结合下面else部分中的代码理解 
			if(Q[i].op == 1) {
				sum += Q[i].y;
			}
			b[k] = Q[i ++];
		}
		else {
			if(Q[j].op == 2) {
				ans[Q[j].id] -= sum;
			}
			else ans[Q[j].id] += sum;
			//若当前询问是-操作，那么ans[Q[j].id]减去sum值（也就是前半部分的影响）
			//若为+操作，则刚好相反 
			b[k] = Q[j ++];
		}
	} 
	for(int k = l;k <= r;++ k) {
		Q[k] = b[k];//归并排序的合并部分
		//为了保证当前递归的上一层可以快速进行，需要让Q[l~r]有序
		//结合函数开头理解 
	}
	return ;
}
int main() {
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
	n = read();
	for(int i = 1;i <= n;++ i) {
		int x = read();
		Q[++ cnt] = query(1 , 0 , i , x);
	}
	m = read();
	for(int i = 1;i <= m;++ i) {
		char c[10];
		scanf("%s",c + 1);
		int x = read(),y = read();
		if(c[1] == 'A') {
			Q[++ cnt] = query(1 , 0 , x , y);
		}
		else {
			Q[++ cnt] = query(2 , ++ tot , x - 1 , 0);
			Q[++ cnt] = query(3 , tot , y , 0);
		}
	}
	solve(1 , cnt);
	for(int i = 1;i <= tot;++ i)print(ans[i]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整 数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点： 0 ， 1 ，……， L （其中 L 是桥的长度）。坐标为 0 的点表示桥的起点，坐标为 L 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是 S 到 T 之间的任意正整数（包括 S,T ）。当青蛙跳到或跳过坐标为 L 的点时，就算青蛙已经跳出了独木桥。题目给出独木桥的长度 L ，青蛙跳跃的距离范围 S,T ，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。输入文件的第一行有一个正整数 L （ 1 <= L <= 10^9 ），表示独木桥的长度。第二行有三个正整数 S ， T ， M ，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中 1 <= S <= T <= 10 ， 1 <= M <= 100 。第三行有 M 个不同的正整数分别表示这 M 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。输出文件只包括一个整数，表示青蛙过河最少需要踩到的石子数。

【输入样例】                【输出样例】                                    对于30%的数据，L <= 10000；

10                                  2                                                      对于全部的数据，L <= 10^9。

2 3 5

2 3 5 6 7

30分解（基础DP）：

      通过对题目的观察我们可以很快发现可以使用动态规划来解决这道题目，我们把每一个桥上的点踩过石子的次数视作前s至t个点踩过石子的次数，若这一个点上有石子则将这个值+1，选择这个点最少的石子次数，最终根据题意输出数轴上第l至l+t个点上最少的石子次数。

ans[i]=min(ans[i],ans[j])      i-t<=j<=i-s              第i个点没有石子           边界:ans[0]=0

ans[i]=min(ans[i],ans[j]+1)  i-t<=j<=i-s              第i个点有石子

50分解（特殊数据）：

         在刚刚不优化DP的情况下我们可以发现一种特殊情况，即s=t，在这种情况下，我们只能选且必选数轴上为s倍数的点，因此只需要计算所有为s倍数点上石子数的和就能够直接得到答案。（注：在下一种做法中该特殊数据需要特判）

正解：状压DP

      根据前面的基本动态规划，我们可以直接看出O(L)的令人绝望的时间复杂度和a[L]的巨大数组，于是我们需要对其进行比较大的优化。

      回想一下刚开始的样例，我们可以发现，在第2个点之后每一个点都必定可以到达，所以我们可以尝试将中间部分大量的没有石子的空白区域跳过节省时间和空间消耗。

   首先我们将s和t的关系分为三种情况：

      ①：t-s=1

             在这种情况下，我们可以比较快速的得到在第t*s-t-s个是最后一个不可拼出的数，即第t*s-t-s+1及以后的点均必可跳到，我们可以选择将这一段到下一个石子处压缩为一步来减少时间消耗。

  ②：t-s>1

          这种情况是一定会优于情况①的，因为我们完全可以仅取第s和s+1个跳跃点，所以这种情况可以省略。

  ③：s=t

       当s=t时很明显是不可能取到s+1的，但由于这种情况易于解决所以只需要加个特判即可。

数学证明：

px+(p+1)y=gcd(p,p+1)是有整数解的，即可得：px+(p+1)y=s是一定有整数解的。

设px+(p+1)y=s的解为：x=x0+(p+1)t,y=y0−pt。令0<=x<=p(通过增减t个p+1来实现)，s>p∗(p+1)−1,

则有：y=s−pxp+1>=s−p2p+1>p∗(p+1)−1−pxp+1>=0

即表示，当s>=p∗(p+1)时，px+(p+1)y=s有两个非负整数解，每次走p步或者p+1步，p∗(p+1)之后的地方均能够到达。

如果两个石子之间的距离大于p∗(p+1)，那么就可以直接将他们之间的距离更改为p∗(p+1)。

综上，得到压缩路径的方法：若两个石子之间的距离>t∗(t−1)，则将他们的距离更改为t∗(t−1)。

因为t<=10，因此我们可以直接将大于10*9的距离直接化为90.