首页 > 代码库 > POJ 3017 Cut the Sequence
POJ 3017 Cut the Sequence
POJ 3017 Cut the Sequence
/** POJ 3017 Cut the Sequence http://poj.org/problem?id=3017 解题思路:单调队列 解题分析: dp[i]=dp[j]+max(j+1,i) //限制条件sum(j+1,i)<m 这样全部的最优决策都在区间为(j+1,i)的单调队列中 dp[i]=min(dp[q[i-1]]+a[q[i]]) i为队列中的决策点 */ #include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<set> #define maxn 100100 #define ll long long using namespace std; ll n,m; int a[maxn]; int q[maxn],boq[maxn]; ll dp[maxn]; ll sum[maxn]={0}; //boq[rear] = if q.size()>1 q[rear-1] else q 区间的前一个位置 multiset<ll> mst; //队列中存在的“位置”的最优解集合 multiset<ll> ::iterator it; ll solve(){ mst.clear(); int bo=0;//队列区间起始位置的上一个位置 int head=0,rear=0; for(int i=1;i<=n;i++){ while(sum[i]-sum[bo]>m) bo++; while(head<rear && q[head]<=bo){ it=mst.find(dp[boq[head]]+a[q[head]]); mst.erase(it); head++; } while(head<rear && a[q[rear-1]]<=a[i]){ it=mst.find(dp[boq[rear-1]]+a[q[rear-1]]); mst.erase(it); rear--; } q[rear]=i; if(head<rear) boq[rear]=q[rear-1]; else boq[rear]=bo; mst.insert(dp[boq[rear]]+a[i]); rear++; if(boq[head]<bo){ it=mst.find(dp[boq[head]]+a[q[head]]); mst.erase(it); boq[head]=bo; mst.insert(dp[boq[head]]+a[q[head]]); } it=mst.begin(); dp[i]=*it; } return dp[n]; } int main(){ while(~scanf("%lld%lld",&n,&m)){ int flag=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; if(a[i]>m) flag=1; } if(flag) printf("-1\n"); else { ll ans=solve(); printf("%lld\n",ans); } } return 0; }
POJ 3017 Cut the Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。