西安响应式网站建设服务提供商,php 做的应用网站,ui网站建设站评价,自己做的免费的网站天天重发好吗[ARC074C] RGB Sequence
Solution
显然是一道dpdpdp#xff0c;我们发现直接维护当前状态有多少种颜色不好维护#xff0c;因为颜色只有333种#xff0c;所以可以直接记录每一种颜色最晚在哪里出现#xff0c;令fi,j,k,lf_{i,j,k,l}fi,j,k,l表示前iii个里RRR最晚在jjj我们发现直接维护当前状态有多少种颜色不好维护因为颜色只有333种所以可以直接记录每一种颜色最晚在哪里出现令fi,j,k,lf_{i,j,k,l}fi,j,k,l表示前iii个里RRR最晚在jjjBBB最晚在kkkGGG最晚在lll。
我们发现状态是O(n4)O(n^4)O(n4)的但是显然有很多冗余状态因为必然有一种颜色在iii所以其中一维不用记录直接用fi,j,kf_{i,j,k}fi,j,k表示前iii个中一种颜色在iii一种在jjj一种在kkk看情况转移即可。
对于限制(l,r,x)(l,r,x)(l,r,x)只需要把不满足条件的fr,j,kf_{r,j,k}fr,j,k的值变为000即可。
时间复杂度O(n3n2m)O(n^3n^2m)O(n3n2m)。
Code
#include vector
#include list
#include map
#include set
#include deque
#include queue
#include stack
#include bitset
#include algorithm
#include functional
#include numeric
#include utility
#include sstream
#include iostream
#include iomanip
#include cstdio
#include cmath
#include cstdlib
#include cctype
#include string
#include cstring
#include ctime
#include cassert
#include string.h
//#include unordered_set
//#include unordered_map
//#include bits/stdc.h#define MP(A,B) make_pair(A,B)
#define PB(A) push_back(A)
#define SIZE(A) ((int)A.size())
#define LEN(A) ((int)A.length())
#define FOR(i,a,b) for(int i(a);i(b);i)
#define fi first
#define se secondusing namespace std;templatetypename Tinline bool upmin(T x,T y) { return yx?xy,1:0; }
templatetypename Tinline bool upmax(T x,T y) { return xy?xy,1:0; }typedef long long ll;
typedef unsigned long long ull;
typedef long double lod;
typedef pairint,int PR;
typedef vectorint VI;const lod eps1e-11;
const lod piacos(-1);
const int oo130;
const ll loo1ll62;
const int mods1e97;
const int MAXN600005;
const int INF0x3f3f3f3f;//1061109567
/*--------------------------------------------------------------------*/
inline int read()
{int f1,x0; char cgetchar();while (c0||c9) { if (c-) f-1; cgetchar(); }while (c0c9) { x(x3)(x1)(c^48); cgetchar(); }return x*f;
}
vectorPR V[MAXN];
int f[305][305][305];
int upd(int x,int y) { return xymods?xy-mods:xy; }
signed main()
{int nread(),mread();for (int i1;im;i){int lread(),rread(),xread();V[r].PB(MP(l,x));}f[1][0][0]3;for (int i1;in;i)for (int j0;ji;j)for (int k0;ki;k) {for (auto v:V[i]) if ((iv.fi)(jv.fi)(kv.fi)!v.se) f[i][j][k]0;if (!f[i][j][k]) continue;f[i1][j][k]upd(f[i1][j][k],f[i][j][k]);f[i1][i][k]upd(f[i1][i][k],f[i][j][k]);f[i1][j][i]upd(f[i1][j][i],f[i][j][k]);}int ans0;for (int i0;in;i)for (int j0;jn;j) ansupd(ans,f[n][i][j]);printf(%d\n,ans);return 0;
}
