做网站什么东西需要费用,网站建设人力成本费用,wordpress虎嗅,阿里云虚拟主机多网站吗原文链接www.cnblogs.com/zhouzhendong/p/UOJ196.html 题解 先离散化#xff0c;设离散化后的值域为 $[0,m]$ 。 首先把问题转化一下#xff0c;变成#xff1a;对于每一个位置 $i$ #xff0c;求出它最终不超过 $j$ 的方案数。 考虑如何求这个东西。 对于一个固定的 $j$ 设离散化后的值域为 $[0,m]$ 。 首先把问题转化一下变成对于每一个位置 $i$ 求出它最终不超过 $j$ 的方案数。 考虑如何求这个东西。 对于一个固定的 $j$ 考虑一个这样的过程 初始时有若干个区间两两不相交且区间内的元素都小于等于 $j$ 而且每一个区间都不能在满足条件的基础上向左右任意一侧扩张。 考虑其中的一个区间 $[L,R]$ 如果出现了操作使得它的边界变成了比 $j$ 大的值那么这个区间会缩小。 考虑对于他的所有子区间 $[x,y]$ 求出 $q$ 次操作之后 $[L,R]$ 缩小成 $[x,y]$ 的方案数。 这东西显然可以列出 DP 方程设 $dp[x][i][j]$ 表示当前进行了 $x$ 次操作初始区间变成 $[i,j]$ 方案数则 $$\begin{eqnarray*}dp[x][i][j]\left (\frac{(i-1)i}2 \frac{(j-i1)(j-i2)}2 \frac {(n-j)(n-j1)}2 \right )dp[x-1][i][j] \\ \sum_{kL}^{i-1} dp[x-1][k][j] \cdot (k-1) \\ \sum_{kj1}^R dp[x-1][i][k] \cdot (n-k) \end{eqnarray*}$$ 这样的话看上去总的运算量是 $O(n^4)$ 的。 考虑到题目中保证数据随机。 那么如果对序列建一棵笛卡尔树那么这个笛卡尔树是基本平衡的可以近似看做一棵满二叉树。 而我们要求的区间只有 $O(n)$ 个是对于每一个位置 $i$ 到它两侧第一个比他大的数之前这个范围内的区间答案。 这个东西放在笛卡尔树上就是子树的size而对一个区间进行dp的复杂度是 $O(q\cdot size^2)$ 又由于这棵笛卡尔树可以近似看做满二叉树所以求个和就可以发现复杂度总和是 $O(n^2q)$ 的可以通过此题。 代码 #pragma GCC optimize(Ofast,inline)
#include bits/stdc.h
#define clr(x) memset(x,0,sizeof (x))
#define For(i,a,b) for (int ia;ib;i)
#define Fod(i,b,a) for (int ib;ia;i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define _SEED_ (CLYAKIOI)
#define outval(x) printf(#x %d\n,x)
#define outvec(x) printf(vec #x );for (auto _v : x)printf(%d ,_v);puts()
#define outtag(x) puts(----------#x----------)
#define outarr(a,L,R) printf(#a[%d...%d] ,L,R);\For(_v2,L,R)printf(%d ,a[_v2]);puts();
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector int vi;
LL read(){LL x0,f0;char chgetchar();while (!isdigit(ch))f|ch-,chgetchar();while (isdigit(ch))x(x1)(x3)(ch^48),chgetchar();return f?-x:x;
}
const int N405,mod1e97,INFmod;
void Add(int x,int y){if ((xy)mod)x-mod;
}
void Del(int x,int y){if ((x-y)0)xmod;
}
int Pow(int x,int y){int ans1;for (;y;y1,x(LL)x*x%mod)if (y1)ans(LL)ans*x%mod;return ans;
}
int n,q;
int a[N];
int val[N][N];
vector int Ha;
int tmp[N][N];
int dp[2][N][N];
void solve(int L,int R,int t){For(i,L,R)For(j,i,R)dp[0][i][j]0;dp[0][L][R]1;For(c,1,q){int _0(c^1)1,_1c1;For(i,L,R)For(j,i,R)dp[_1][i][j](LL)tmp[i][j]*dp[_0][i][j]%mod;For(j,L,R){int s0;For(i,L,j){Add(dp[_1][i][j],s);Add(s,(LL)dp[_0][i][j]*(i-1)%mod);}}For(i,L,R){int s0;Fod(j,R,i){Add(dp[_1][i][j],s);Add(s,(LL)dp[_0][i][j]*(n-j)%mod);}}}For(j,L,R){int s0;For(i,L,j){Add(s,dp[q1][i][j]);Add(val[i][t],s);}}
}
int main(){nread(),qread();For(i,1,n)a[i]read(),Ha.pb(a[i]);sort(Ha.begin(),Ha.end());Ha.erase(unique(Ha.begin(),Ha.end()),Ha.end());For(i,1,n)a[i]lower_bound(Ha.begin(),Ha.end(),a[i])-Ha.begin();For(i,1,n)For(j,1,n)tmp[i][j](i-1)*i/2(j-i1)*(j-i2)/2(n-j)*(n-j1)/2;a[0]a[n1]Ha.size();For(t,0,(int)Ha.size()-1){int L0,Mx0;For(R,1,n1)if (a[R]t)Mxmax(Mx,a[R]);else {if (L1R-1){if (Mxt){For(i,L1,R-1)Add(val[i][t],val[i][t-1]);}elsesolve(L1,R-1,t);}LR,Mx0;}}For(i,1,n){int ans0;Fod(j,(int)Ha.size()-1,1)Del(val[i][j],val[i][j-1]);For(j,0,(int)Ha.size()-1)Add(ans,(LL)val[i][j]*Ha[j]%mod);printf(%d ,ans);}puts();return 0;
}转载于:https://www.cnblogs.com/zhouzhendong/p/UOJ196.html
