1.状态机模型：https://codeforces.com/contest/1984/problem/C2
记一下max与min状态转移即可，下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[200010],t,n;
ll dp[200010][2];//dp[i][0]表示min,dp[i][1]表示max
ll cnt[200010][2];//cnt[i][0]表示取到dp[i][0]的方法数，cnt[i][1]表示取到dp[i][1]的方法数
ll mod=998244353;
int main()
{
cin>>t;
while(t--){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
dp[1][0]=a[1];
if(a[1]>=0) cnt[1][0]=2;
else cnt[1][0]=1;
if(a[1]>=0) cnt[1][1]=2;
else cnt[1][1]=1;
dp[1][1]=abs(a[1]);
for(int i=2;i<=n;i++)
{
dp[i][0]=(dp[i-1][0]+a[i]);
if(dp[i][0]>=0) cnt[i][0]=cnt[i-1][0]*2%mod;
else cnt[i][0]=cnt[i-1][0];
dp[i][1]=max(abs(dp[i-1][0]+a[i]),dp[i-1][1]+a[i]);
if(dp[i][1]==dp[i-1][1]+a[i]&&dp[i][1]==abs(dp[i-1][0]+a[i]))
{
if(dp[i-1][1]!=dp[i-1][0])
{
cnt[i][1]=2*cnt[i-1][1]%mod;
if(dp[i-1][0]+a[i]>=0) cnt[i][1]=(cnt[i][1]+2*cnt[i-1][0]%mod)%mod;
else cnt[i][1]=(cnt[i][1]+cnt[i-1][0])%mod;
}
else{
cnt[i][1]=2*cnt[i-1][1]%mod;
}
}
else if(dp[i][1]==dp[i-1][1]+a[i])
{
cnt[i][1]=2*cnt[i-1][1]%mod;
}
else{
if(dp[i-1][0]+a[i]>=0) cnt[i][1]=2*cnt[i-1][0]%mod;
else cnt[i][1]=cnt[i-1][0];
}
}
cout<<cnt[n][1]<<endl;
}
}2.DFS：https://codeforces.com/contest/1975/problem/D
首先先让红蓝相遇，然后再遍历一遍树，下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
vector<int> edge[200010];
int t,n,a,b,x,y;
int cnt;
int track[200010];
int h[200010];
int dis;
void dfs(int x,int cnt1,int fa)//两点相差的距离
{
if(a==x){
cnt=cnt1;
track[a]=fa;
return;
}
for(int i=0;i<edge[x].size();i++)
{
int son=edge[x][i];
if(son==fa) continue;
track[son]=x;
dfs(son,cnt1+1,x);
}
}
void dfs1(int x,int fa)//建树高度
{
h[x]=0;
for(int i=0;i<edge[x].size();i++)
{
int son=edge[x][i];
if(son==fa) continue;
dfs1(son,x);
h[x]=max(h[x],h[son]+1);
}
}
int dfs3(int x,int fa){
int res=0;
for(int i=0;i<edge[x].size();i++){
int son=edge[x][i];
if(son==fa) continue;
res+=2+dfs3(son,x);
}
return res;
}
int dfs2(int x,int fa){
int k=-1;//记录最长链
int lon=-1;
for(int i=0;i<edge[x].size();i++){
int son=edge[x][i];
if(son==fa) continue;
if(h[son]>lon){
lon=h[son];
k=i;
}
}
int res=0;
for(int i=0;i<edge[x].size();i++){
int son=edge[x][i];
if(son==fa) continue;
if(i==k) res+=1+dfs2(son,x);
else res+=dfs3(son,x)+2;
}
return res;
}
int find(int start,int dis){
if(dis==0) return start;
return find(track[start],dis-1);
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
cin>>a>>b;
dis=0;
vector<int>::iterator it;
memset(edge,0,sizeof(edge));
for(int i=1;i<=n-1;i++)
{
cin>>x>>y;
edge[x].push_back(y);
edge[y].push_back(x);
}
//找出蓝点到红点的距离
cnt=0;
dfs(b,0,-1);
dis=cnt/2;
int ck=find(a,dis);
dfs1(ck,-1);
if(cnt%2==0) dis+=dfs2(ck,-1);
else dis+=1+dfs2(ck,-1);
cout<<dis<<endl;
}
}3.区间DP：https://codeforces.com/contest/1969/problem/C
我们令dp[i][j]表示前i个用<=j次的min，对于状态的更新，我们考虑dp[i][k]的第i个元素，我们发现假如没有次数限制对于长度n我们用最坏用n-1可以更新到min，回过头来，假如进行t次操作，一定可以让最后长度t+1的一段变成这个区间中最小的值，于是我们枚举t，它可以让最后t+1个变成其中的min,具体地，我们不妨令k=2(k>=3同理）,那么所有的答案可能的情况就是倒数3个变成其中min,倒数2个变成其中min以及最后一个没有变的3种情况，消耗的次数分别为2，1，0（最优答案一定是其中一个）
或者说，我们从集合的角度分析，所有涉及到a[i]的可能（没涉及的就是dp[i-1][j]+a[i])：
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,k;
ll a[300010][13];
ll b[300010];
ll dp[300010][11];
int main()
{
cin>>t;
while(t--){
cin>>n>>k;
for(ll i=1;i<=n;i++) cin>>b[i];
//搜索每一个点的前k+1个内的min
for(ll i=1;i<=n;i++){
ll ans=b[i];
for(ll j=1;j<=k+1;j++){
ans=min(ans,b[max((ll)1,i-j+1)]);
a[i][j]=ans;
}
}
/*for(int i=1;i<=n;i++){
cout<<endl;
for(int j=1;j<=k+1;j++) cout<<a[i][j]<<" ";
}
*/
//开始DP
for(ll i=0;i<=k;i++) dp[1][i]=b[1];
for(ll i=2;i<=n;i++){
for(ll j=0;j<=k;j++){
dp[i][j]=dp[i-1][j]+b[i];
for(ll w=1;w<=j;w++){
if(i-(w+1)<0){
dp[i][j]=min(dp[i][j],a[i][k+1]*i);
}
else dp[i][j]=min(dp[i][j],dp[i-w-1][j-w]+a[i][w+1]*(w+1));
}
}
}
cout<<dp[n][k]<<endl;
}
}4.模拟（类似DP转移的思想）：https://codeforces.com/contest/1976/problem/C
我们先枚举第n+m+1走的答案，然后对于前面的一个人退出，看看有没有想选这个但是被迫走的，有的化取最近的更新，下面的一个空位由n+m+1填，反之若没有就只好让n+m+1来填，同时从后往前依次更新被迫的人的位置。下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,a[300010],b[300010],n,m;
bool wh[300010];
ll cnt1,cnt2;
int main()
{
cin>>t;
while(t--)
{
ll ans[200020]={0};
cin>>n>>m;
for(ll i=1;i<=n+m+1;i++) cin>>a[i];
for(ll i=1;i<=1+n+m;i++) cin>>b[i];
//计算dp[n+m+1]
ll cnt1=0,cnt2=0;
ll res=0;
for(ll i=1;i<=n+m;i++)
{
if(a[i]>b[i]&&cnt1<n){
cnt1++;
wh[i]=0;
res+=a[i];
}
else if(a[i]>b[i])
{
cnt2++;
wh[i]=1;
res+=b[i];
}
else if(a[i]<b[i]&&cnt2<m){
cnt2++;
wh[i]=1;
res+=b[i];
}
else{
cnt1++;
wh[i]=0;
res+=a[i];
}
}
ans[n+m+1]=res;
//转移
ll ca=n+m+1,cb=n+m+1;//ca:最先被迫编程的
for(ll i=n+m;i>=1;i--){
ll hh=res;
if(cb==n+m+1&&wh[i]==0) hh+=a[n+m+1]-a[i];
else if(ca==n+m+1&&wh[i]) hh+=b[ca]-b[i];
else if(wh[i]) hh+=abs(a[ca]-b[ca])-b[i]+a[n+m+1];
else hh+=abs(a[cb]-b[cb])-a[i]+b[n+m+1];
if(wh[i]&&a[i]>b[i]) cb=i;
if(!wh[i]&&a[i]<b[i]) ca=i;
ans[i]=hh;
}
for(ll i=1;i<=n+m+1;i++) cout<<ans[i]<<" ";
cout<<endl;
}
}
