1. 首先，复赛的时候

注意时间复杂度和空间大小

1.看题目时必须仔细,例如数组的大小在空间允许的情况下，多开10倍

2.如果采用暴力算法，记得剪枝或者记忆化

2.关于区间dp

常规模版：

1
2
3
4
for ...//枚举区间长度
	for ...//枚举左右两个端点
    		for ...//枚举断点，或者直接dp
    			dp方程

推导方程的思路

1.运用数组，灵活表示当前的状态

例如P1880 [NOI1995]石子合并

设置 $f1[i][j]$
代表第 $i\sim j$ 这个区间，石子合并的最大值
设置 $f2[i][j]$
代表第 $i\sim j$这个区间，石子合并的最小值

通过题意得知，总价值=合成石子的数量的和
所以枚举一个中间点 $k$ (断点)
$f[i][j]=\max(f[i][j],val[l][k] + val[k + 1][r] + merge(l, k, k + 1, r))$

所以 $dp$ 是一个由小规模向大规模推导的过程

用数组或其他来描述当前的状态

3.关于记忆化

关于记忆化模板

1
2
3
4
5
6
7
8
9
10
11
12
dfs(参数){
	if(保存过)
	return 之前的值;
   if(达到终点) return 根据题意;//比如1
	int sum=0;
	for 
		...
		 sum+=dfs(参数);
	// 搜索之后的答案，保存
	记忆化数组=sum;
	return sum; 
}

如何写出记忆化（对作者而言）

首先 你需要一个好老师

思路：

先写出暴力,再加以改进

关于暴力的模板

1
2
3
4
5
6
7
8
dfs(参数){
	if(达到条件)
	return 
	for
		...
		dfs(参数); 
		回溯 ;
}

我们可以发现暴力和记忆化的模板只差几句话

$\color{red}\text{关键是在于如何表示状态，例如：状压等。}$

关于暴力的注意事项：

1.有时候题目要求的是需要循环的回溯，例如：排序等。

2.有时就不需要用循环，直接在dfs中运用参数就行了

==但是这就有很大的差异，前者是以n为底数，基本上是n^2或n!==

==后者却只有2^n==

==时间复杂度相差极高，分数相差在40分以上==

这个是很多年以前的东西，这里稍微补充一点减少歧义。

就是对于暴力来说在内部进行循环复杂度显然是 $O(n^{dep})$。这里注意一点
$\Omega(n^n) \ne \Omega(n!)$，也就是说两者的复杂度差异其实是很大的。所以能少循环一点就少循环一点。

其次对于 $2^n$ 和 $n!$ 往往是部分分的几种情况，比如说动态规划问题，可以考虑对于集合进行记忆化这样复杂度就是 $O(2^n)$ 不然直接暴力枚举的话肯定是 $O(n!)$。