首页 > 代码库 > BZOJ 1122 POI2008 账本BBB 单调队列

BZOJ 1122 POI2008 账本BBB 单调队列

题目大意:给定一个由+1<script type="math/tex" id="MathJax-Element-517">+1</script>和?1<script type="math/tex" id="MathJax-Element-518">-1</script>构成的长度为n<script type="math/tex" id="MathJax-Element-519">n</script>的序列,提供两种操作:
1.将某一位取反,花销为x<script type="math/tex" id="MathJax-Element-520">x</script>
2.将最后一位移动到前一位。花销为y<script type="math/tex" id="MathJax-Element-521">y</script>
要求终于p+sumn=q<script type="math/tex" id="MathJax-Element-522">p+sum_n=q</script>。且p+sumi0(1in)<script type="math/tex" id="MathJax-Element-523">p+sum_i\geq 0(1\leq i\leq n)</script>,求最小花销
枚举终于的序列以哪个点開始。那么从这个点往后的最小前缀和能够用单调队列预处理出来
然后贪心地把左边的?1<script type="math/tex" id="MathJax-Element-524">-1</script>改成+1<script type="math/tex" id="MathJax-Element-525">+1</script>。右边的+1<script type="math/tex" id="MathJax-Element-526">+1</script>改成?1<script type="math/tex" id="MathJax-Element-527">-1</script>直到满足要求就可以

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 2002002
using namespace std;
int n,p,q;
long long x,y,ans=0x7fffffffffffffffll;
char s[M];
int sum[M],_min[M];
void Assert(bool flag)
{
    if(flag)
        return ;
    printf("%d\n",1/0);
    exit(0);
}
int main()
{
    int i;
    cin>>n>>p>>q>>x>>y;
    scanf("%s",s+1);
    for(i=n<<1;i>n;i--)
        sum[i]=sum[i+1]+(s[i-n]==‘-‘?-1:1);
    for(i=n;i;i--)
        sum[i]=sum[i+1]+(s[i]==‘-‘?

-1:1); static int q[M],r,h; for(i=n<<1;i;i--) { while( r-h>=1 && sum[q[r]]<sum[i] ) q[r--]=0; q[++r]=i; while( q[h+1]-i>n ) q[++h]=0; if(i<=n) _min[i]=sum[i]-sum[q[h+1]]; } Assert( ~ (::q)-p - sum[n+1] & 1 ); int temp=(::q-p)-sum[n+1]>>1; for(i=1;i<=n;i++) { long long cost=(n-i+1)%n*y+abs(temp)*x; _min[i]+=p+max(temp,0)*2; if(_min[i]<0) cost+=(1-_min[i]>>1)*x*2; if(cost<ans) ans=cost; } cout<<ans<<endl; return 0; }

<script type="text/javascript"> $(function () { $(‘pre.prettyprint code‘).each(function () { var lines = $(this).text().split(‘\n‘).length; var $numbering = $(‘
    ‘).addClass(‘pre-numbering‘).hide(); $(this).addClass(‘has-numbering‘).parent().append($numbering); for (i = 1; i <= lines; i++) { $numbering.append($(‘
  • ‘).text(i)); }; $numbering.fadeIn(1700); }); }); </script>

BZOJ 1122 POI2008 账本BBB 单调队列