一句话概括动态 dp：用来解决带修改/多次区间询问的 dp 问题。将转移写成矩阵的形式，然后利用线段树求解区间问题/单点修改
1814E
注意一条边要么选 2 要么选 0 次，而且第一条边一定是选了 2 次。如果有一条边没选，那么这条边两侧的边一定都选了。
设 \(f_i\) 代表考虑到第 \(i\) 条边，且这条边必选。显然有 \(f_i=\min(f_{i-1}, f_{i-2}) + a_i\)，注意这里是只算了一次，所以最后需要乘以 2
这个转移明显可以写成广义矩阵乘法的形式（广义矩阵乘法：\(C_{i,j} = \min(A_{i,k}+B_{k,j})\)）
用线段树维护每个点的矩阵。注意初始化，必有 \(f_1=a_1, f_2=a_1+a_2\)，一个比较巧妙的方法是利用递推关系求出来 \(f_{-1}=0, f_0=+\infty\)
每次单点修改的时候就把线段树上对应结点的矩阵修改即可。
其中 \(X\) 就是 \(1\cdots n-1\) 的矩阵的广义乘积，最后答案就是 \(f_{n-1}\) 也就是 \(X_{0,1}\)
代码：
// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long LL;
const int INF = 0x3f3f3f3f, maxn = 2e5+5;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n,qu;
char s[maxn];
struct mat{
ll a[2][2];
mat(){memset(a,0x3f,sizeof a);}
}a[maxn];
struct segm{
mat sum;
}se[maxn << 2];
mat operator * (mat a,mat b){
mat c;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
return c;
}
void build(int l,int r,int num){
if(l == r){
se[num].sum = a[l];
return ;
}
int mid = l+r>>1;
build(l,mid,num<<1);build(mid+1,r,num<<1|1);
se[num].sum = se[num << 1].sum * se[num << 1|1].sum;
}
void update(int k,int l,int r,int num){
if(l == r){
se[num].sum = a[k];
return ;
}
int mid=l+r>>1;
if(k <= mid)update(k,l,mid,num<<1);
else update(k,mid+1,r,num<<1|1);
se[num].sum = se[num << 1].sum * se[num << 1|1].sum;
}
signed main(){
scanf("%d",&n);
vector<int>b(n+1);
-- n;
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
a[i].a[0][0] = a[i].a[1][0] = b[i];
a[i].a[0][1] = 0, a[i].a[1][1] = inf;
}
build(1,n,1);
scanf("%d",&qu);
while(qu --){
int k,x;scanf("%d%d",&k,&x);
a[k].a[0][0] = a[k].a[1][0] = x;
update(k,1,n,1);
printf("%lld\n",se[1].sum.a[1][0]*2);
}
return 0;
}
750E
考虑 \(f_{i,0/1/2/3/4}\) 表示当前满足匹配 2017 的极大子序列是 空集/2/20/201（且没有6）/2017
转移方程：
很明显可以写成 5*5 的矩阵转移的形式，每次按当前位来决定转移矩阵
区间查询的时候就相当于查询区间的广义矩阵乘积，线段树维护即可。
// by SkyRainWind
#include <bits/stdc++.h>
#define mpr make_pair
#define debug() cerr<<"Yoshino\n"
#define pii pair<int,int>
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long LL;
const int inf = 1e9, INF = 0x3f3f3f3f, maxn = 2e5+5;
int n,qu;
char s[maxn];
struct mat{
int a[5][5];
mat(){memset(a,0x3f,sizeof a);}
}a[maxn];
struct segm{
mat sum;
}se[maxn << 2];
mat operator * (mat a,mat b){
mat c;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
for(int k=0;k<5;k++)
c.a[i][j] = min(c.a[i][j], a.a[i][k] + b.a[k][j]);
return c;
}
void build(int l,int r,int num){
if(l == r){
se[num].sum = a[l];
return ;
}
int mid = l+r>>1;
build(l,mid,num<<1);build(mid+1,r,num<<1|1);
se[num].sum = se[num << 1].sum * se[num << 1|1].sum;
}
mat query(int x,int y,int l,int r,int num){
if(x <= l && r <= y){
return se[num].sum;
}
int mid=l+r>>1;
if(y <= mid)return query(x,y,l,mid, num<<1);
else if(x>mid)return query(x,y,mid+1,r,num<<1|1);
return query(x,y,l,mid,num<<1) * query(x,y,mid+1,r,num<<1|1);
}
signed main(){
scanf("%d%d",&n,&qu);
scanf("%s",s + 1);
for(int i=1;i<=n;i++){
for(int j=0;j<=4;j++)a[i].a[j][j] = 0;
if(s[i] == '2')a[i].a[0][0] = 1, a[i].a[0][1] = 0;
if(s[i] == '0')a[i].a[1][1] = 1, a[i].a[1][2] = 0;
if(s[i] == '1')a[i].a[2][2] = 1, a[i].a[2][3] = 0;
if(s[i] == '7')a[i].a[3][3] = 1, a[i].a[3][4] = 0;
if(s[i] == '6')a[i].a[3][3] = 1, a[i].a[4][4] = 1;
}
build(1,n,1);
while(qu --){
int l,r;scanf("%d%d",&l,&r);
mat v = query(l,r,1,n,1);
printf("%d\n",v.a[0][4] >= INF ? -1 : v.a[0][4]);
}
return 0;
}