题解：AT_arc211_c [ARC211C] Forest

· · 题解

感谢样例 3 送我 C 的 600 分，而不是像 CCF 那样在 NOI plus T2 题面放弱样例让我虚空思考结果害的我想假全场，我正式比赛的 rp 全转移到日常公开赛了是吧。

分析一下性质，很难不发现，砍树每次一定只砍一段连续的树才最优，且每段空地只有最大值才会用上。直接考虑如何达到最大收益，显然可以贪心地考虑，注意到每次砍一段前提下，无论从哪边砍过来，都会使得任何一段初始空地连续段有至少一次贡献，故我们应使全局最大值创造最大价值。

在简单情形下（忽略原来是树的位置的数对后续的影响），具体而言，记砍的次数为 cnt，包含全局最大值初始空地连续段数为 num，我们需让全局最大值创造出 cnt+num-1 的贡献，则全局最大值每次都要创造贡献。

还要考虑样例 3 所示情形，即存在最大值所在位置原来是树。根据样例猜测既可每次利用全局最大值，亦可先把被覆盖的调出来。下证该结论正确性。如上文所述，任何一段初始空地连续段都会有至少一次贡献，而砍出被覆盖的全局最大值后两边空地产生一次贡献后就不再产生贡献，且不对其他空地最优贡献数产生影响，故与利用全局最大值等效，结论得证。

答案的具体统计是显然的，考虑符合上述要求的相邻初始空地连续段对第一步方案数的贡献是两个区间分别的区间内最大值个数相乘。

当然注意一个细节：边界的树不会被砍掉，故计算全局最大值时要屏蔽这些数。（我为了这个细节多花了 15min）

::::success[code]


#include<bits/stdc++.h>
using namespace std;
int n,r[200010],cnt[200010],j,_max[200010],max_,ll,rr;
long long ans;
string s;
int main()
{cin>>n>>s;s=" "+s;
 bool wa=false;
 for(int i=1;i<s.size();i++)
 if(wa==false&&s[i]=='.') wa=true,ll=i;
 wa=false;
 for(int i=s.size()-1;i>=1;i--)
 if(wa==false&&s[i]=='.') wa=true,rr=i;
 for(int i=1;i<=n;i++)
 cin>>r[i];
 for(int i=ll;i<=rr;i++)
 max_=max(max_,r[i]);
 j=0;s[0]='#';
 for(int i=1;i<=n;i++)
 {if(s[i]=='.'&&s[i-1]=='#') j++;
  if(s[i]=='.')
  {if(r[i]>_max[j])
   {_max[j]=r[i];
    cnt[j]=1;
   }
   else if(r[i]==_max[j])
   cnt[j]++;
  }
 }
 j=0;bool ac=false;
 for(int i=1;i<=n;i++)
 {if(s[i]=='.'&&s[i-1]=='#')
  {j++;
   if(ac==true||_max[j]==max_)
   ans+=(long long)cnt[j-1]*cnt[j];
   if(_max[j]==max_)
   ac=true;
   else
   ac=false;
  }
  if(s[i]=='#'&&r[i]==max_) ac=true;
 }
 cout<<ans;
}