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个内的minfor(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]<<" ";}*///开始DPfor(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;}
}