poj 3017

本文主要是介绍poj 3017，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：给你n个数，求划分的区间所有的最大值之和（划分条件就是这个区间之和小于m），使其最小

首先很容易想到dp，公式 dp【i】= min（dp【i】，dp【j】+max（a【j+1】+。。。a【i】））

这是O(n^2)的复杂度

那么维护一个单调递减的序列的话，每次求的就是单调队列里面满足条件的那些元素，然后根据dp递推公式求解

Hint  ：用多组交的话会wA

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define ll long long
#define N 111111
const ll inf = 1111111111111;ll sum;
ll a[N];
int n;
ll m;
int que[N];
ll dp[N];ll slove(){sum = 0;int k  = 0;int l = 0;int r = -1;dp[0] = 0;for(int i=1;i<=n;i++){scanf("%I64d",&a[i]);if(a[i]>m) return -1;sum+=a[i];while(sum>m) sum-=a[++k]; //求满足区间和小于m的区间左端while(l<=r&&a[que[r]]<=a[i]) --r;//更新单调队列，即那些比a【i】小的元素都可以舍弃掉了，因为之后不会再用了que[++r] = i;while(l<=r&&que[l]<=k) l++;dp[i] = inf;int h = k;// printf(" h ---%d\n l--%d--r---%d\n%d\n",h,l,r,que[r]);for(int j=l;j<=r;j++){ll tmp = dp[h] + a[que[j]];if(tmp < dp[i]) dp[i] = tmp;h = que[j];}}return dp[n];
}int main(){scanf("%d%I64d",&n,&m);printf("%I64d\n",slove());
}

这篇关于poj 3017的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---