当前位置: 首页 > news >正文

如何迅速k掉网站室内设计学校排名

如何迅速k掉网站,室内设计学校排名,wordpress 主题制作 教程,外贸营销方式有哪些传送门 [前题提要]:感觉dp还是很显然的,感觉单调栈也不是很难想,但是VP的时候脑子比较乱,dp方程想偏了,没写出来… 看完题目,不难发现应该存在一种递推关系.因为会发现最后剩下来的必然是原序列的一种子序列,然后这种子序列计数的问题.应该想到使用dp计数. 刚开始我的想法是使…传送门 [前题提要]:感觉dp还是很显然的,感觉单调栈也不是很难想,但是VP的时候脑子比较乱,dp方程想偏了,没写出来… 看完题目,不难发现应该存在一种递推关系.因为会发现最后剩下来的必然是原序列的一种子序列,然后这种子序列计数的问题.应该想到使用dp计数. 刚开始我的想法是使用 d p [ i ] dp[i] dp[i]记录前 i i i位的方案数,然后发现这种方式极难递推.给两个 h a c k hack hack样例: 2 4 1 3 2 1发现光光使用上面的dp方程,对于上述两种样例没办法区分. 所以考虑优化一下我们的dp方程,使用 d p [ i ] dp[i] dp[i]来记录前 i i i位并且最后一位是 i i i的子序列个数. 然后想一下该怎么进行转移,对于当前位置 i i i,如果它能从 j j j位置转移过来,需要满足什么条件. 首先我们区间 [ j 1 , i − 1 ] [j1,i-1] [j1,i−1]的所有数应该是小于我们的 a [ j ] , a [ i ] a[j],a[i] a[j],a[i]的,这样我们才能使用端点将区间中的所有数字删掉.也就是说,我们的所有能转移的 j 1 , j 2 , j 3 . . . j n j_1,j_2,j_3...j_n j1​,j2​,j3​...jn​必须满足 a [ j 1 ] a [ j 2 ] . . . a [ j n ] a [ i ] a[j_1]a[j_2]...a[j_n]a[i] a[j1​]a[j2​]...a[jn​]a[i] 不难发现,我们的 a [ j n ] a[j_n] a[jn​]应该是 i i i位置左边第一个小于 a [ i ] a[i] a[i]的数.这个我们可以使用单调栈预处理出来(使用单调栈倒推即可,此处不在赘述).然后我们会发现 [ j n , i − 1 ] [j_n,i-1] [jn​,i−1]的所有数字都可以转移过来(中间数被 a [ i ] a[i] a[i]位置的数字删掉),然后对于上述的 j 1 j_1 j1​~ j n − 1 j_{n-1} jn−1​(注意此处是单点),也都可以转移过来.并且除了上述的点以外,没有一个点能转移到 i i i,因为对于其他点来说,区间中一定有一个点的值比端点小. 对于区间 [ j n 1 , i ] [j_n1,i] [jn​1,i]的贡献,我们可以使用前缀和处理一下 对于所有单点贡献 ∑ d p [ j i ] \sum dp[j_i] ∑dp[ji​],我们也可以使用前缀和处理,只不过此时的前缀和的下标变了而已. 需要注意的是我们最后剩下来的数字必然是后缀最小值,所以最终我们的答案是就是所有后缀最小值的贡献和 下面是具体的代码部分: #include bits/stdc.h using namespace std; typedef long long ll; #define root 1,n,1 #define ls (rt1) #define rs (rt1|1) #define lson l,mid,rt1 #define rson mid1,r,rt1|1 inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w; } inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100); } #define maxn 1000000 #define int long long const int mod998244353; const double eps1e-8; #define int_INF 0x3f3f3f3f #define ll_INF 0x3f3f3f3f3f3f3f3f int p[maxn];int dp[maxn];int sum1[maxn],sum2[maxn]; signed main() {int Tread();while(T--) {int nread();mapint,intpos;for(int i1;in;i) {p[i]read();pos[p[i]]i;}stackints;mapint,intmp;s.push(p[n]);for(int in-1;i1;i--) {while(!s.empty()p[i]s.top()) {mp[s.top()]i;s.pop();}s.push(p[i]);}dp[1]1;sum1[1]1;sum2[1]1;for(int i2;in;i) {dp[i](sum1[i-1]-sum1[mp[p[i]]]mod)%mod;dp[i](dp[i]sum2[mp[p[i]]])%mod;if(mp[p[i]]0) dp[i](dp[i]1)%mod;sum2[i](sum2[mp[p[i]]]dp[i])%mod;sum1[i](sum1[i-1]dp[i])%mod;}int minnp[n];int ans0;for(int in;i1;i--) {minnmin(minn,p[i]);if(minnp[i]) {ans(ansdp[i])%mod;}}coutansendl;for(int i1;in;i) {dp[i]0;sum1[i]sum2[i]0;}}return 0; }
http://www.huolong8.cn/news/448594/

相关文章:

  • 怎么做qq钓鱼网站吗wordpress 显示备案
  • 营销网站策划网站风格总结
  • 青岛公司网站设计许昌网站设计制作
  • 做电商有哪些网站深圳网站建设分期付
  • 网站如何快速推广淘宝网页设计尺寸
  • 商标注册查询官方网站成都网站seo服务
  • 云南做网站报价个人做门户网站需要注册
  • 创建一个网站的创业计划书公众号第三方建微网站
  • 医院网站建设方案策划书wordpress出现不能登录界面
  • 网站建设安全级别济南电视台新闻频道
  • 网站建设 东阿阿胶wordpress安装显示404
  • 芯片商城网站建设中国机械加工网官方
  • 株洲网站优化工程公司经营范围
  • 登封网站建设网站制作软件
  • 优化网站打开速度西安网站开发建设
  • html5手机网站调用微信分享微信投票网站制作
  • 网站开发 asp.net 还要学什么wordpress插件video playe
  • 旅游网站的功能设计用asp.net做的网站有哪些
  • 成都那家做网站好?wordpress简单用户积分
  • 网站建设套路wordpress 修改文件名
  • 汕头网站制作电话广州做韩国网站
  • 网站建设公司电话销售客源哈尔滨专业制作网站制作
  • 外贸网站 服务器ios网站开发教程
  • 免费域名网站黄的免费精品网的功能和服务
  • 怎么样优化网站seowordpress分页导航插件
  • 自适应网站制作简创网络网页制作个人主页素材
  • 织梦网站优化怎么做带后台的网站建设
  • 网站建设公司新报申请网站步骤
  • 信云科技的vps怎么做网站网站开发模板图片
  • 小企业网站建设哪找wordpress主题使用加