傳送門

$dp$簡單題，才不是因為我去打答案的表才沒去想正解呢

考慮一個四維$dp$

$f[pos][i][j][k]$表示當前處理到$pos$，三種顏色分別最近一次出現的位置是$i,j,k$時的方案數

很明顯這個$dp$是正確的（廢話）

每次我們枚舉當前位置并加給下一個可能被轉移的狀態

但這樣O(n4)O(n^4)O(n4)明顯會超時

我們發現$pos$只會是$max(i,j,k)$，所以可以省去第一維

對于每個限制的話，我們考慮對于每個點$i$維護所有滿足$r=i$的限制

枚舉所有限制，看$i,j,k\in [l,r]$的數量是否為$v$

不滿足設為0就可以了

#include<bits/stdc++.h> using namespace std; inline int read(){char ch=getchar();int res=0;while(!isdigit(ch))ch=getchar();while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();return res; } const int N=305; const int mod=1e9+7; int f[N][N][N],n,m,ans; #define mp make_pair #define pi pair<int,int> vector<pi>vec[N]; inline bool check(int i,int j,int k){int p=max(i,j);p=max(p,k);int len=vec[p].size();for(int h=0;h<len;h++){int l=vec[p][h].first,v=vec[p][h].second;int num=0;if(i>=l)num++;if(j>=l)num++;if(k>=l)num++;if(num!=v)return false;}return true;} int main(){n=read(),m=read();for(int i=1;i<=m;i++){int l=read(),r=read(),v=read();vec[r].push_back(mp(l,v));}f[0][0][0]=1;for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){if(!f[i][j][k])continue;if(!check(i,j,k)){f[i][j][k]=0;continue;}int p=max(i,j);p=max(p,k);if(p==n)ans=ans+f[i][j][k],ans%=mod;p++;f[p][j][k]=(f[p][j][k]+f[i][j][k])%mod;f[i][p][k]=(f[i][p][k]+f[i][j][k])%mod;f[i][j][p]=(f[i][j][p]+f[i][j][k])%mod;}}}cout<<ans; }

轉載于:https://www.cnblogs.com/stargazer-cyk/p/10366322.html

總結

以上是生活随笔為你收集整理的【第一届“文翁杯”现场竞技赛】(校内“欢乐”赛)T1—洗刷刷（dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。