LIS：最长上升子序列
Prince and Princess
本题可以将 $LCS$ （最长公共子序列）问题转换成 $LIS$ 问题。
我们可以根据第一个字符串进行新的编号，由先后顺序更新第二个字符串的编号，保证了单调的性，所以直接在第二个字符串中找最长不下降子序列即可。
最长上升子序列
再找最长上升子序列时，只用找到比我们存的数小的，就更新。可能不符合真正的最长上升序列，甚至不合法。但是它合理的原因是，他为的是保存最长上升的长度，如果有更长的子序列合法，那么就可以更新它的长度。
要想更新它的长度就要比现有的数都大，那么这个数一定会出现在合理的最长上升子序列中，所以这么存的长度合法。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=2e5+10;
int t,n,p,q,a[o_o],b[o_o],c[o_o];
int n_m[o_o],x_p,s_m;
void n_w(){
memset(n_m,0,sizeof(n_m));
x_p=s_m=0;
for(int i=1;i<=p;i++)n_m[a[i]]=++x_p;//第一个数列编新编号
for(int i=1;i<=q;i++)//第二个序列更新所有编号
if(n_m[b[i]])c[++s_m]=n_m[b[i]];//存到新数组中
}
int a_s,z_k[o_o];
void g_a(){
a_s=1;//初始化答案（序列第一位相同）
z_k[1]=c[1];//最长上升子序列第一位初始化
for(int i=2;i<=s_m;i++){
if(c[i]>z_k[a_s])z_k[++a_s]=c[i];//可以保持上升，存入
else {//不能保持上升
int p_s=lower_bound(z_k+1,z_k+1+a_s,c[i])-z_k;//找到第一个比他小的
z_k[p_s]=c[i];//更新数组
}
}
}
int main(){
scanf("%d",&t);
for(int k=1;k<=t;k++){
n=r_r(),p=r_r(),q=r_r();
p++,q++;
for(int i=1;i<=p;i++)a[i]=r_r();//读入第一个数组
for(int i=1;i<=q;i++)b[i]=r_r();//读入第二个数组
n_w();//赋新编号
g_a();//找结果
printf("Case %d: %d\n",k,a_s);//输出
}
return 0;
}LCS：最长公共子序列
History Grading
枚举匹配位置，记录匹配结果，继承状态。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int n,t,d_p[31][31],n_m[31],t_p[31];
int main(){
n=r_r();
for(int i=0;i<n;i++){
int x_x=r_r();
n_m[x_x-1]=i;//按顺序标号正确答案
}
while(cin>>t){
t_p[t-1]=0;
for(int i=1;i<n;i++){//按顺序标号学生答案
int x_x=r_r();
t_p[x_x-1]=i;
}
memset(d_p,0,sizeof d_p);//多测清空
for(int i=0;i<n;i++){//枚举学生答案位置
for(int j=0;j<n;j++){//枚举答案位置
if(n_m[j]==t_p[i])d_p[i+1][j+1]=d_p[i][j]+1;//匹配成功，答案更新
else d_p[i+1][j+1]=max(d_p[i][j+1],d_p[i+1][j]);//那个匹配成功的多继承那个状态
}
}
printf("%d\n",d_p[n][n]);//输出所有答案与所有学生答案位置都匹配过的答案
}
return 0;
}区间DP
石子合并
先枚举块长（从短到长），再枚举所有区块，枚举断点，计算每个区块的断点左半部分和右半部分，记上每次合并后的价值。所有元素都可能作为开头，所以都要找一遍，记录答案。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=201;
const int a_x=0x3f3f3f3f;
int n,m_i,m_a,f_1[o_o][o_o],f_2[o_o][o_o],n_m[o_o];
int s[o_o];
int main(){
n=r_r();
for(int i=1;i<=n;i++){
n_m[i]=r_r();//读入原序列
n_m[i+n]=n_m[i];//双倍长度方便计算以每个元素开头的情况
}
for(int i=1;i<=n*2;i++)s[i]=s[i-1]+n_m[i];//计算前缀和
for(int p=1;p<n;p++){//枚举区块长
for(int i=1,j=i+p;(j<n*2)&&(i<n*2);i++,j=i+p){//在序列中枚举区块
f_2[i][j]=a_x;//初始赋最大值，找最小值
for(int k=i;k<j;k++){//枚举断点，从左右两部分找最优解继承
f_1[i][j]=max(f_1[i][j],f_1[i][k]+f_1[k+1][j]+s[j]-s[i-1]);//找最大值，通过前缀和快速计算区间和（合并石子得到的价值）
f_2[i][j]=min(f_2[i][j],f_2[i][k]+f_2[k+1][j]+s[j]-s[i-1]);//找最小值
}
}
}
m_i=a_x;//初始赋最大值，找最小值
for(int i=1;i<=n;i++){//遍历每个元素开头的情况，找到真正的最优解
m_a=max(m_a,f_1[i][i+n-1]);
m_i=min(m_i,f_2[i][i+n-1]);
}
printf("%d\n%d",m_i,m_a);
return 0;
}能量项链
分开看，每个珠子就是一颗珠子，而不去考虑前后问题，再遍历区间的时候处理即可。
只要枚举区间，枚举断点，根据题目描述更新最大值即可。题目计算能量的方法，正好是枚举左端点（前一个珠子的头标记），断点 $+1$ （前一个珠子的尾标记，后一个珠子的头标记），右端点 $+1$ （后一个珠子的尾标记）的能量积。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=201;
int n;
int a_a[o_o];
int d_p[o_o][o_o];
int m_a=-1;
int main(){
n=r_r();
for(int i=1;i<=n;i++)a_a[i]=r_r(),a_a[i+n]=a_a[i];//存两边，方便枚举每个开头的情况
for(int i=2;i<2*n;i++){//枚举结尾
for(int j=i-1;i-j<n&&j>=1;j--){//在长度范围内，枚举左区间
for(int k=j;k<i;k++)//枚举断点
//左边最大值 + 右边最大值 + 加持能量（题目中描述） 更新最大值
d_p[j][i]=max(d_p[j][i],d_p[j][k]+d_p[k+1][i]+a_a[j]*a_a[k+1]*a_a[i+1]);
if(d_p[j][i]>m_a)m_a=d_p[j][i];//更新答案
}
}
cout<<m_a<<endl;
return 0;
}Coloring Brackets
初始化所有新遍历到的括号，从大区间向小遍历，最后回溯时，等新答案，做后统计答案输出即可。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int m_a=1001;
const int m_d=1e9+7;
int n,g_y[m_a];//存配对括号互存下标
long long d_p[m_a][m_a][3][3];//存情况
char s[m_a];//读入括号序列
stack<int>s_t;//用于匹配括号
void d_f(int l,int r){
if(l+1==r)//是相邻的一对括号，初始化
d_p[l][r][0][1]=d_p[l][r][0][2]=d_p[l][r][1][0]=d_p[l][r][2][0]=1;
else if(g_y[l]==r){//现在左右是一对括号
d_f(l+1,r-1);//更新左右端点
for(int i=0;i<=2;i++)//枚举状态可能，更新答案
for(int j=0;j<=2;j++){
if(j!=1)//现在右括号和匹配左括号不同色，统计答案
d_p[l][r][0][1]=(d_p[l][r][0][1]+d_p[l+1][r-1][i][j])%m_d;
if(j!=2)//现在右括号和匹配左括号不同侧，统计答案
d_p[l][r][0][2]=(d_p[l][r][0][2]+d_p[l+1][r-1][i][j])%m_d;
if(i!=1)//现在左括号和匹配右括号不同色，统计答案
d_p[l][r][1][0]=(d_p[l][r][1][0]+d_p[l+1][r-1][i][j])%m_d;
if(i!=2)//现在左括号和匹配右括号不同色，统计答案
d_p[l][r][2][0]=(d_p[l][r][2][0]+d_p[l+1][r-1][i][j])%m_d;
}
}
else{
d_f(l,g_y[l]);//更新左括号匹配的范围
d_f(g_y[l]+1,r);//匹配左括号匹配的右括号外的下标，继续匹配。
for(int i=0;i<=2;i++)//枚举第一对括号的左括号
for(int j=0;j<=2;j++)//枚举第一对括号的右括号
for(int p=0;p<=2;p++)//枚举第二对括号的左括号
for(int q=0;q<=2;q++){//枚举第二对括号的右括号
if((j==1&&p==1)||(j==2&&p==2)) continue;//匹配相邻同色跳过
d_p[l][r][i][q]=(d_p[l][r][i][q]+d_p[l][g_y[l]][i][j]*d_p[g_y[l]+1][r][p][q]%m_d)%m_d;//合法更新答案
}
}
}
int main(){
scanf("%s",s);
n=strlen(s);//读取原串
for(int i=0;i<n;i++){//匹配括号，互存另一半括号下标
if(s[i]=='(')s_t.push(i);
else g_y[s_t.top()]=i,g_y[i]=s_t.top(),s_t.pop();
}
d_f(0,n-1);//从边界开始查询方案数
long long a_s=0;
//由于括号染两种颜色的没有存，所以是 0，不影响统计结果
for(int i=0;i<=2;i++)//枚举左括号染色情况
for(int j=0;j<=2;j++)//枚举右括号染色情况
a_s=(a_s+d_p[0][n-1][i][j])%m_d;//统计所有情况
printf("%lld\n",a_s);//输出结果
return 0;
}压缩
区间枚举块长，左端点，找到压缩后的最短长度更新。难点在于区间内有 $M$ 的压缩，要考虑新压缩后的长度与原压缩的那个短，不断取最优。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=101;
using namespace std;
char s_s[o_o];
int d_p[o_o][o_o][3];
int n;
int f_i(int l,int r){
if((r-l+1)&1)return 0;//长度是奇数，不可能压缩
int m_i=(l+r)>>1;//找到查抄串的一半处
for(int i=l;i<=m_i;i++)//前后匹配
if(s_s[i]!=s_s[i+m_i-l+1])return 0;//前后不同，不能压缩
return 1;//压缩成功
}
int main(){
scanf("%s",s_s+1);//读取字符串
n=strlen(s_s+1);//获取字符串长度
memset(d_p,0x3f,sizeof(d_p));//初始化
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
d_p[i][j][0]=d_p[i][j][1]=(j-i+1);//初始化区间长度
for(int l_n=2;l_n<=n;l_n++)//枚举长度
for(int l=1;l+l_n-1<=n;l++){//枚举左端点
int r=l+l_n-1;//右端点
if(f_i(l,r))d_p[l][r][0]=min(d_p[l][(l+r)>>1][0]+1,d_p[l][r][0]);//查找成功，更新比对压缩户后的长度
//枚举断点，更新答案
for(int k=l;k<r;k++)//区间内没有 M（压缩开头）
d_p[l][##r][0]=min(d_p[l][r][0],d_p[l][k][0]+r-k);//查找区间内压缩后的最小值
for(int k=l;k<r;k++)//区间内有 M（压缩开头）
//更新端点左边有 M 和没有 M 的最小值，和右边有 M 和没有 M 的最小值的总的最小值（抽象：选择 M 的放置地点）
d_p[l][r][1]=min(d_p[l][r][1],min(d_p[l][k][0],d_p[l][k][1])+min(d_p[k+1][r][0],d_p[k+1][r][1])+1);
}
printf("%d\n",min(d_p[1][n][1],d_p[1][n][0]));
return 0;
}树形DP
“访问”美术馆
枚举将时间分给两个儿子（向左，向右走），暴力统计最大值即可。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1001;
int d_p[o_o][o_o];
struct po{
int l_n,v;//道路花费时间，画的数量
}p_p[o_o<<4];
int s_m;
int l_l(int k){//左儿子
return k<<1;
}
int r_r(int k){//右儿子
return k<<1|1;
}
void yv(int x){
p_p[x].l_n=r_r(),p_p[x].v=r_r();
p_p[x].l_n<<=1;//一去一回，两倍
if(!p_p[x].v){//若为零说明是走廊（见题目）
yv(l_l(x));//左儿子
yv(r_r(x));//右儿子
}
}
int d_f(int x,int s_m){
if(d_p[x][s_m]>0||!s_m)return d_p[x][s_m];//已经遍历过或时间已经耗尽返回
if(p_p[x].v){//是展室
d_p[x][s_m]=min(p_p[x].v,(s_m-p_p[x].l_n)/5);//剩下的时间是全拿，还是来这里之后拿能拿部分（来这里要花费时间）
return d_p[x][s_m];
}
for(int k=0;k<=s_m-p_p[x].l_n;k++)//枚举剩下时间，分给两儿子
d_p[x][s_m]=max(d_p[x][s_m],d_f(l_l(x),k)+d_f(r_r(x),s_m-p_p[x].l_n-k));//取最大能拿到的画
return d_p[x][s_m];
}
int main(){
s_m=r_r()-1;//要在警察到来前跑走（-1）
yv(1);//读入
printf("%d",d_f(1,s_m));//从第一条走廊开始找
return 0;
}Book of Evil
先找到里根节点最远的点，在以这个点为跟，重新跑一遍，更新新深度。再找最深的节点，以这个节点为根节点，在新数组中重新跑一遍深度。这样，可以知道每个点距离两个最远互相怪物的点的距离，若最远的点符合要求，那么就合法。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<stack>
using namespace std;
long long r_r(){//快读
long long x=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
const int o_o=1e5+10;
struct po{
int v,n_t;
}p_p[o_o<<1];
int n,m,d,s_m,t_p,a_s;
int v_l[o_o],d_p_1[o_o],d_p_2[o_o],h_d[o_o];
void a_d(int u,int v){
p_p[++s_m].n_t=h_d[u];
p_p[s_m].v=v;
h_d[u]=s_m;
}
void d_1(int u,int f_a,int d_p){
d_p_1[u]=d_p;//存深度
for(int i=h_d[u];i;i=p_p[i].n_t){
int v=p_p[i].v;//下一个点
if(v!=f_a)d_1(v,u,d_p+1);//不返回走过的点
}
}
void d_2(int u,int f_a,int d_p){//找深度
d_p_2[u]=d_p;//存深度
for(int i=h_d[u];i;i=p_p[i].n_t){
int v=p_p[i].v;//下一个点
if(v!=f_a)d_2(v,u,d_p+1);//不返回走过的点
}
}
int main(){
n=r_r(),m=r_r(),d=r_r();
for(int i=1;i<=m;i++)v_l[i]=r_r();//存初始怪物生成地点
for(int i=1;i<n;i++){//连边
int u=r_r(),v=r_r();
a_d(u,v);
a_d(v,u);
}
d_1(1,0,0);//从一节点开始找
for(int i=1;i<=m;i++)//找到怪物中深度最大的点
if(d_p_1[v_l[i]]>d_p_1[t_p])t_p=v_l[i];
d_1(t_p,0,0);//从怪物最大深度的点开始找，重新赋值深度
t_p=0;//清零
for(int i=1;i<=m;i++)//找到怪物中深度最大的点
if(d_p_1[v_l[i]]>d_p_1[t_p])t_p=v_l[i];
d_2(t_p,0,0);//继续找点离这个点的深度
for(int i=1;i<=n;i++)//从第一个点开始找，若距离都符合，计数
if(d_p_1[i]<=d&&d_p_2[i]<=d)a_s++;
printf("%d\n",a_s);
return 0;
}
