前言
本文章将会持续更新，主要是一些个人觉得比较妙的题，主观性比较强（给自己记录用的），有讲错请补充。
带 ！号的题是基础例题，带 * 号的是推荐首先完成的题（有一定启发性的）。
动态规划
线性动态规划
! Jury Compromise(蓝书例题)
看到题目比较容易的想到：
定义：f[i][j][k] 为 \(i\) 表示考虑到第 \(i\) 个候选人，\(j\) 表示当前辩方总分为 \(j\)，\(k\) 表示当前控方总分为 \(k\) 时是否可行。
得到方程式：
\[f[i][j][k]=f[i][j][k] or f[i-1][j-d[i]][k-p[i]] \]dp 后枚举绝对值大小判断是否可行。
时间是足够的，但我们还可以优化空间。
设 f[j][k] 表示在前 \(i\) 个人中选 \(j\) 个人，辩方控方之差为 \(k\)，可辩方与控方之和的最大值。
得到方程式：
\[f[j][k]=max(f[j][k],f[j-1][k-(d[i]-p[i])]+d[i]+p[i] \]初始：\(f[0][0]=0\)，其它均为正无穷。
这就像 01 背包了，所以 \(j\) 也要倒序枚举。
但此题还要输出方案，所以还要定义一个数组 d[i][j][k]，表示 f[j][k] 的最大值是从哪一位候选人转移过来的（注意要输出方案的题都要把每一位状态都记录下来，滚动数组会覆盖一些信息）。
最后递归求解。
注意 \(k\) 可能是负的，要有一个偏移量 base，f[j][k] 变成 f[j][k+base]。
Coins（蓝书例题）
P6064 [USACO05JAN] Naptime G（蓝书例题）
先把环变成链，由于这么做第一个小时一定是不计入贡献的（就算是在睡觉，也是入睡的第一个小时，没有贡献），所以再做一次 dp，第二次强制规定熟睡。
The least round way
因为只有 \(2 \times 5\) 会在末尾添加 \(0\),所以先求出每个点的 \(5\) 与 \(2\) 的因数个数，然后 dp 。
设 \(f[0][i][j]\) 为到 \(i,j\) 这个位置 \(2\) 的最小因数和，\(f[1][i][j]\) 为到 \(i,j\) 这个位置 \(5\) 的最小因数和，最后比较两者的最小值，即为答案。
注意如果有 \(0\)，只要走了 \(0\) 就后面都是 \(0\)，即答案为 \(1\)，所以上面的答案与 \(1\) 比较，取最小值。
此题要输出方案，所以递归求解就行。
注：此题的 dp 只能分开求，不能合起来求，因为这样求的只是局部最优，而无法通过这一个推到下一个（可能这个点是因数 \(2\) 最小，下一个点又是因数 \(5\) 最小，可能这个点的因数 \(5\) 的个数来更新下一个点更优）。
至于可以分开求的原因：最后求的都是因数 \(2\)、因数\(5\) 单个的最小值，输出路径时是沿着最小的那个输出的，那另一个因数在此路径上的值肯定大于等于单个求出的值，但不印象答案的变化。
个人错点：在判 \(0\) 前就输出答案，相当于没判 \(0\)。
code
#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
int n,flag,op;
int num[2][N][N],f[2][N][N];
bool vis[N][N];
int get(int x,int k)
{
int res=0;
while(x%k==0) res++,x/=k;
return res;
}
void print(int i,int j,int k)
{
if(i==1&&j==1)
{
if(k) printf("R");
else printf("D");
return ;
}
if(i==1) print(i,j-1,1);
else if(j==1) print(i-1,j,0);
else if(f[op][i][j]==f[op][i-1][j]+num[op][i][j]) print(i-1,j,0);
else if(f[op][i][j]==f[op][i][j-1]+num[op][i][j]) print(i,j-1,1);
if(i!=n||j!=n)
if(k) printf("R");
else printf("D");
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int x;
scanf("%d",&x);
if(!x) flag=i,vis[i][j]=1,num[1][i][j]=num[0][i][j]=1;
else num[0][i][j]=get(x,2),num[1][i][j]=get(x,5);
}
for(int i=1;i<=n;++i)
f[0][0][i]=f[0][i][0]=f[1][0][i]=f[1][i][0]=2e9+10;
f[0][1][1]=num[0][1][1],f[1][1][1]=num[1][1][1];
for(int i=1;i<=n;i++)
for(int j=(i==1?2:1);j<=n;j++)
{
f[0][i][j]=min(f[0][i-1][j],f[0][i][j-1])+num[0][i][j];
f[1][i][j]=min(f[1][i-1][j],f[1][i][j-1])+num[1][i][j];
}
int ans=min(f[0][n][n],f[1][n][n]);
if(flag&&ans>1)
{
puts("0");
for(int i=1;i<flag;i++) printf("D");
for(int i=1;i<n;i++) printf("R");
for(int i=flag+1;i<=n;i++) printf("D");
return 0;
}
printf("%d\n",ans);
if(f[0][n][n]>f[1][n][n]) op=1;
else op=0;
print(n,n,0);
return 0;
}
Modular Sequence
构造的每一个数的都是：\(x/y+k\times y,k \in N\)，并且除了开头都是一个个等差数列加起来。
可以算出 \(k\) 的总数 \(s\)，再预处理出可以构成 \(1\) 到 \(s\) 的最短序列长度。
式子为：
\[f[i]=min(f[i],f[i-get(j)]+j+1 \]\(get(j)\) 等于 \((j+1)*j/2\)。
最后枚举开头等差数列的结尾，这里总和记为 \(sum\)，只要有满足 \(f[s-sum]<=n-i\) 就找到符合要求的序列，再递归输出方案即可。
时间复杂度：\(O(n \sqrt s)\)。
P7690 [CEOI2002] A decorative fence
我们可以一位一位的填木板，就像“试填法”。但是看 \(C\) 的范围是大于 int 范围一个一个求太慢了，所以想到倍增。
用倍增预处理出第一个木板\(1\)到\(N\)的所有情况，因为还要区分这个数的前后两位是比它高还是低所以还要存这个木板是处于高位还是低位，用\(1,0\)表示。
所以很容易想出状态 \(f[ i ][ j ][ k ]\) ，表示用 \(i\) 块木板拼成栅栏其中最左边的长度从小到大在第 \(j\) 位，并且状态为 \(k\) (\(k\) 指是处于高位还是低位)。
这里特别强调 \(j\) 是从小到大的第 \(k\) 位而不是木板真实的长度。因为如果是真实的长度，每一个个状态是唯一的，就是和暴力枚举是一样的，不方便倍增计数。
这里第 \(j\) 大的有点像离散化思想，把真实的值用从大到小的编号相互映射，以达到减少枚举数量的目的。
状态转移方程：
\[f [ i ][ j ][ 0 ] = \sum_{p=j}^{i-1} f [ i - 1 ][ p ][ 1 ] \]\[f [ i ][ j ][ 1 ] = \sum_{p=1}^{j-1} f [ i - 1 ][ p ][ 0 ] \]第一个实在是当前为低位时，那它的前一个就是高位并比它高。
第二个式子是当前为高位是，那它的前一个就是低位并比它低。
当倍增处理后只需要从小到大依次减去个数，从而求出第 \(C\) 小的排列（有一点像数位dp），当然每减去一次，\(k\) 就要取反一次，因为每一块木板肯定是高低交错的。
时间复杂度：预处理 \(O(N^{3})\)，求答案时 \(O(N^{2})\) 。
一些细节看代码注释。
code
#include<bits/stdc++.h>
using namespace std;
int T,n;
bool vis[30];
long long m,f[30][30][2];
void get_f()//预处理
{
f[1][1][0]=f[1][1][1]=1;//初始化
for(int i=2;i<=20;i++)
for(int j=1;j<=i;j++)
{
for(int k=j;k<=i-1;k++)
f[i][j][0]+=f[i-1][k][1];
for(int k=1;k<=j-1;k++)
f[i][j][1]+=f[i-1][k][0];
}
}
int main()
{
cin>>T;
get_f();
while(T--)
{
memset(vis,0,sizeof vis);//多组数据要清空
cin>>n>>m;
int las,k;//las指当前数字，k指状态（高位还是低位）
//一位一位的找，先找第一位
for(int j=1;j<=n;j++)
{
if(f[n][j][1]>=m)//为了使字典序更小必须k是1开头，就是后面一位是低位
{
las=j;
k=1;
break;
}
else m-=f[n][j][1];
if(f[n][j][0]>=m)
{
las=j;
k=0;
break;
}
else m-=f[n][j][0];
}
vis[las]=1;//vis是来存是否出现过，因不能有重复
cout<<las<<" ";
//找后面几位
for(int i=2;i<=n;i++)
{
k^=1;//必须是一个高位一个低位
int j=0;//j是枚举前i位，这个数的排位
for(int l=1;l<=n;l++)//l是当前的真实长度
{
if(vis[l])continue;//找过了就不着了
j++;
if(k==0&&l<las||k==1&&l>las)//0,1分两种考虑
{
if(f[n-i+1][j][k]>=m)
{
las=l;
break;
}
else m-=f[n-i+1][j][k];
}
}
vis[las]=1;
cout<<las<<" ";
}
puts("");
}
return 0;
}
! P2657 [SCOI2009] windy 数
注：古早文章，写的很烂。此篇文章只是讲解了记忆化搜索的代码，和可能有点用的小总结。
记忆化搜索
#include<bits/stdc++.h>
using namespace std;
int q[20];
int f[20][20][2][2];
int a,b;
int n;
int dfs(int len,int las,bool flag,bool ze)
{
if(!len)return 1;
if(~f[len][las][flag][ze])return f[len][las][flag][ze];//前面搜过了就直接放回值
int sum=0;
for(int i=0;i<=9;i++)
{
if((!flag||i<=q[len])&&(ze||abs(i-las)>=2))
sum+=dfs(len-1,i,flag&&(i==q[len]),ze&&(i==0));
}
f[len][las][flag][ze]=sum;
return sum;
}
int work(int x)
{
memset(q,0,sizeof q);
memset(f,-1,sizeof f);
n=0;
while(x)
{
q[++n]=x%10;
x/=10;
// cout<<q[n];
}
// cout<<endl;
return dfs(n,11,1,1);
}
int main()
{
cin>>a>>b;
cout<<work(b)-work(a-1);
return 0;
}
数位dp,记忆化搜索常用套路
1 dfs中设置几个变量
（1）len 位数，现在是第几位。
（2）las 上一个数是什么，通常题目的限制条件是与前一位的关系。
（3）flag 指有没有限制，通常是以从高到低位枚举的如果上一位没有到最大限制。
这一位可以填\(0-9\)（题目中的限制不包括）。
（4）ze 有没有前置\(0\)，如果有前置\(0\)，不能充当首位，但可以去更新位数更大的数。
本题代码中几个难懂的点
1.
if((!flag||i<=q[len])&&(ze||abs(i-las)>=2))
!flag||i<=q[len]:没有限制，前一位没到最高或有限制但这一位没到限制。
ze||abs(i-las)>=2:有前导0都可以填或有限制但满足条件。
2.
sum+=dfs(len-1,i,flag&&(i==q[len]),ze&&(i==0));
flag&&(i==q[len]):前面有限制（前面的位数都到了最高位）并且这一位也到最高位，后面有限制。
ze&&(i==0):前面有前导 \(0\) ，并且这一位也是 \(0\)，就附上 \(0\) 。
树形动态规划
! P3177 [HAOI2015] 树上染色
此题把黑点与黑点，白点与白点的边权和，转化成每条边对整体的边权和的影响。
本质上是一个树形 dp ，把每一条边看作一个物品，求每一个物品对整体的贡献。
设 f[i][j] 为考虑第 $i $ 个结点，其子树中有 \(j\) 个点染成黑色的边权和。
设 \(val=(j*(k-j)+(s[v]-j)*(n-k-(s[v]-j)))\)。
式子为：
\[f[u][i]=max(f[u][i],f[u][i-j]+val*c[e]+f[v][j]); \]时间复杂度：\(O(n^2)\)。
数据结构优化
! P3957 [NOIP2017 普及组] 跳房子
求金币数很难，但如果给出金币数来判断是否能得到 \(k\) 分要容易的多，由此可以想到二分金币数。
设金币数为 \(g\) ，那每次跳的距离的范围为 \([\max(1,d-g),d+g]\) ，很容易想出式子：
\[f_i=f_j+a_i(i-r \le j \le i-l) \]现在时间复杂度为: \(O(\log V \times n^2)\)，\(V\) 指金币的值域，显然是无法通过此题的。
我们发现式子中枚举 \(j\) 的长度是固定，为：\(g \times 2 +1\)，并且是求那一段区间中的最值，这时想到 滑动窗口 那道题，也就想到单调队列。
本题实现有不少细节
-
每次二分前都要把 \(f\) 数组赋为负无穷，因为有无法走到的格子。
-
用双指针维护区间。
-
单调队列一定先从队尾加入（
tail++），再把不在区间的数从对头弹出（head++）。
code
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10,inf=1e9+10;
int n,d,k;
int f[N];
int t[N];
pair<int,int>a[N];
queue<int>q;
bool check(int mid)
{
for(int i=1;i<=n;i++) f[i]=-inf;
int head=1,tail=0;
int l=max(1,d-mid),r=d+mid,i=1,j=0;
f[0]=0;
for(;i<=n;i++)
{
while(a[i].first-a[j].first>=l&&j<i)
{
if(f[j]>-inf)
{
while(tail>=head&&f[j]>=f[t[tail]]) tail--;
t[++tail]=j;
}
j++;
}
while(tail>=head&&a[i].first-a[t[head]].first>r) head++;
if(tail>=head) f[i]=f[t[head]]+a[i].second;
if(f[i]>=k) return 1;
}
return 0;
}
int main()
{
scanf("%d%d%d",&n,&d,&k);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].first,&a[i].second);
}
int l=0,r=inf;
while(l<r)
{
int mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(l==inf) puts("-1");
else printf("%d",l);
return 0;
}
! P2254 [NOI2005] 瑰丽华尔兹
先想暴力，肯定是一个 \(O(n \times m \times T)\) 的 dp 。
\(f[t][i][j]\) 表示在第 \(t\) 时刻在第 \(i\) 行第 \(j\) 列所能获得的最长距离。
转移方程：
\[f[t][i][j]=max(f[t-1][i][j],f[t][i+nt[z][0]][j+nt[z][1]]+1) \]这样可以过 \(50 \%\) 的数据，但对于 \(100 \%\) TLE 且 MLE。
这时就要用到两个常见的优化了：滚动数组优化空间，单调队列优化时间。
滚动数组优化很好理解，因为整个式子的 \(t\) 只用到了 \(t\) 与 \(t-1\)，用一个 \(p\) 表示当前的 \(t\) ，\(p \otimes 1\) 表示 \(t-1\) 即可。
在一段时间内只能向一个方向移动一定的距离，在那中间取最大值，这不就又是滑动窗口，只需要单调队列优化就可以了。
Music Festival
每次取的肯定是每一个集合中单调上升的序列，但这个序列的最小值一定比上一个区间的最大值大。
这可以想到预处理每个集合的最大值、最小值与序列长度。
但最长的序列本不一定会用到每给集合的所有元素，所以我们把每一个集合中的单调上升的序列预处理出来（注最大值的是一定的）。
如：
1 4 3 2 5
有三个序列：
[1 4 5],[4,5],[5]。
然后做一个简单的 dp，可求出答案。
时间复杂度：\(O(n^2)\)。
考虑用树状数组优化：
先按最小值排序，然后每次询问小于最小值的最大值，然后把当前的值插入树状数组中。
时间复杂度：\(O(nlogn)\)。
矩阵优化
*P6772 [NOI2020] 美食家
运用了多种优化技巧，值得学习。
首先写出最朴素的式子：
\[f[i][j+w]=max(f[i][j+w],f[i][j]+c) \]如果有节日加上额外的愉快值。
然后最容易关注到的是 \(T \in 10^9\)，这么大那多半要用矩阵快速幂了。
但递推式是每次更新 \(w\) 后的值，显然无法直接用矩阵来推，但我们又关注到 \(w \le 5\)，那我们用到
技巧1： 拆点。
把一个点 \(u\)，变成\(u_1 → u_2→ ⋯ → u_5\) 的这样一个结构，边权都是 \(0\)。对于一条边 \((u,v,w)\)，我们从 \(u_w\) 向 \(v_1\) 连一条边权为 \(c[v]\) 的边。这样相当于要先 \(u_1\) 走到 \(u_w\)，再从 \(u_w\) 走到 \(v\)，刚好经过了 \(w\) 条边，也就是起到了从 \(f[i]\)转移到 \(f[i+w]\) 的效果。
其实还可以拆边，但此题 \(n < m\)，显然拆点更好。
但矩阵快速幂是来求乘法的，但此题是取 \(max\)，这时用到
技巧2：新定义矩阵。
\[C=A \otimes B= \max_{k=1}^{n} \{ A[i][k]+B[k][j]\} \]注意初始化矩阵也要改变。
这样就可以完成 dp 转移了。
但还有节日怎么算
在原来的方程来看，有节日才才会参与状态转移，加上 \(k\) 的范围也不大，那用普通式子把 &k& 个节日包含进去，也就是：
\[f[t_i]=f[t_{i-1}] \otimes base^{t_i-t_{i-1}} \]此时是拆过点的，然对应的点加上这个值 \(f[t_i][w_i]+=c_i\)。
这时的时间复杂度为 \(O(k \times (5n)^3 \times logT)\)，还是无法通过。
技巧3：二进制拆分。
这在背包中出现过。
\(base^k\) 可以被 \(base^1,base^2,base^3, \cdots base^n\) 表示，把它们都先预处理处理。
时间复杂度降为：\(O((5n)^3 \times logT + k \times (5n)^2 \times logT)\)。
此题被解决。
* P3758 [TJOI2017] 可乐
此题有两个特殊的条件:停止不动和原地爆炸。
有两种除了方式：
第一种：停止不动相当于自己向自己连一条边，原地爆炸相当于每一个点向一个虚点连一条有向边，爆炸后就不能行动了。
第二种：用两个 dp 方程转移，一个指不包含爆炸的，一个指爆炸的方案。
\[f[0][i][u]=f[0][i-1][u]+f[0][i-1][v] \]\[f[1][i][u]=f[1][i-1][u]+f[0][i-1][u] \]时间复杂度： \(O(n^2\times log T)\)。
考虑优化：
一个邻接矩阵的 \(k\) 次方相当于：第 \(i\) 行第 \(j\) 列的数字含义是从 \(i\) 到 \(j\) 经过 \(k\) 步的路径方案总数。
此题题正好运用此点，可以用矩阵快速幂解决。
可能有用的知识：图的矩阵表示
标签：int,好题,len,times,flag,动态,规划,dp,las From： https://www.cnblogs.com/hutongzhou/p/18169026