首页 > 代码库 > poj 3017
poj 3017
n 个数字 m
把n个数字分成一些段 然后每一段的和不能超过m 求分成这些段 每段的最大值 之和 最小
一开始 前缀和 二分 线段树 n *n *log(n) 不出意外吃个TLE 至少有一点长进了
然后看了一下是单调队列
1 显然 每个数都大于m 就不行了
单调队列 维护的是 合法区间里最大的那个数的下标 有点绕 然后有这个点 就可以找到下个区间 (有可能使得值变化的) long long
参考http://blog.csdn.net/sdj222555/article/details/7996970
#include<stdio.h> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> using namespace std; #define ll __int64 #define MAXN 100010 #define inf 200000000000000 ll z[MAXN]; ll dp[MAXN]; int q[2*MAXN]; int main() { ll n,m; scanf("%I64d%I64d",&n,&m); int ok=0; for(int i=1;i<=n;i++) { scanf("%I64d",&z[i]); if(z[i]>m) ok=1; } if(ok==1) { printf("-1\n"); return 0; } for(int i=1;i<=n;i++) dp[i]=inf; int l,r,k; l=0; r=0; k=0; ll sum=0; for(int i=1;i<=n;i++) { sum+=z[i]; while(sum>m) sum-=z[++k]; while(l<=r&&z[q[r]]<=z[i]) r--; q[++r]=i; while(l<=r&&q[l]<k) l++; int kk=k; for(int j=l;j<=r;j++) { ll now=dp[kk]+z[q[j]]; //好好体会 dp[i]=min(dp[i],now); kk=q[j]; //还有这里 } } printf("%I64d\n",dp[n]); return 0; }
poj 2373
显然先dp一下 然后单调队列维护2*b-2*a 里面最小的
#include<stdio.h> #include<algorithm> #include<stdlib.h> #include<cstring> #include<string> #include<cmath> #include<vector> #include<queue> #include<map> #include<iterator> #include<stack> using namespace std; #define ll __int64 #define MAXN 1010010 #define inf 2000000007 #define mod 1000000007 int dp[MAXN]; int q[MAXN]; int a,b,n,l; int solve() { if(l&1) return -1; int st=0,en=-1; int sz=2*b+1; dp[0]=0; for(int i=a;i<=b;i++) if(dp[2*i]<=inf) dp[2*i]=1; int k=2*b-2*a; for(int i=0;i<=k;i+=2) { en++; while(en>st&&dp[q[en-1]]>dp[i]) en--; q[en]=i; while(i-q[st]>=sz) st++; } for(int i=2*b;i<=l;i+=2) { if(i-2*a>k) { en++; while(en>st&&dp[q[en-1]]>dp[i-2*a]) en--; q[en]=i-2*a; while(i-2*a-q[st]>=sz) st++; } while(i-q[st]>=sz) st++; if(dp[i]<=inf) dp[i]=dp[q[st]]+1; } if(dp[l]>=inf) return -1; return dp[l]; } int main() { scanf("%d%d",&n,&l); scanf("%d%d",&a,&b); for(int i=1;i<=l;i++) dp[i]=inf; for(int i=1;i<=n;i++) { int s,e; scanf("%d%d",&s,&e); for(int j=s+1;j<e;j++) dp[j]=inf+1; } printf("%d\n",solve()); return 0; }
poj 3017
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。