poj 3017 Cut the Sequence（单调队列优化）

题目链接：http://poj.org/problem?id=3017

题意：给你一个长度为n的数列，要求把这个数列划分为任意块，每块的元素和小于m，使得所有块的最大值的和最小

分析：这题很快就能想到一个DP方程 f[ i ]=min{ f[ j ] +max{ a[ k ] }}( b[ i ]<j<i,j<k<=i) b[ i ]到 i的和大于m

这个方程的复杂度是O(n^2)，明显要超时的（怎么discuss都说数据弱呢= =）

然后是优化了，首先当然是要优化一个最大值的队列，使得这个队列的队首元素的到当前位置的和不超过m，

这样一个可行解就是，f[ i ]=f[b[ i ]-1]+a[ q[ l ]](即队首元素的值)，

这并不是最优解，所以还要找到队列中的最优解，一个可能的最优解只能是这样的

f[ q[ j ] ]+ a[ q[j +1 ]]，也就是 a[ j ] 要大于后面的数，

很显然，如果a[ j ]小于后面的数，那么我们就可以将 a[ j ] 划分到后面去，而取得更优解

这里涉及的这个找最优解问题；

AC代码：

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 using namespace std;

 typedef long long LL;

 const int N = ;

 LL num[N];

 LL sum[N];

 LL f[N];

 int q[N];

 int main() {

     int n, i, j, st, ed, p;

     LL m;

     while(~scanf("%d%I64d", &n, &m)) {

         memset(f, -, sizeof(f));

         st = , ed = -;

         p = ;

         sum[] = ;

         f[] = ;

         for(i = ; i <= n; ++i) {

             scanf("%I64d", num + i);

             sum[i] = sum[i-] + num[i];// 统计前n项的和

             if(st > ed) {

                 st = , ed = -;

                 q[++ed] = i;

             }

             while(st <= ed && num[i] >= num[q[ed]])   --ed;//单调队列优化

             q[++ed] = i;

             while(sum[i] - sum[p-] > m)    ++p;

             while(st <= ed && p > q[st])    st++;//单调队列里面保存的数已经被删除，则底部++；

             if(st > ed) continue;  //当前队列为空了，直接返回

             if(f[p-] != -) //如果当前p位，有数；

                 f[i] = f[p-] + num[q[st]];

             for(j = st + ; j <= ed; ++j) {

                 if(f[q[j]-] != -)

                     f[i] = min(f[i], f[q[j-]] + num[q[j]]);

             }

         }

         printf("%I64d\n",f[n]);

     }

     return ;

 }

巴特西

poj 3017 Cut the Sequence（单调队列优化）

最新文章

热门文章

巴特西

poj 3017 Cut the Sequence（单调队列优化 ）

最新文章

热门文章

poj 3017 Cut the Sequence（单调队列优化）