CF1814E Chain Chips & CF750E New Year and Old Subsequence - 动态 dp -

一句话概括动态 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;
}