A(fzu 1894)
普通的单调队列,trick是进队判断的符号选取(>=wa , >ac).
B(poj 2823)
没什么好说的 ,坑爹poj g++,tle ;c++,ac.
C(hdu 3415)
尝试封装了一下单调队列。。。感觉也没有方便多少.
#define maxn 100010
#define INF 1000000000
int a[maxn<<],p[maxn<<],n,k; struct Que
{
int q[maxn<<],front,tail,cmp;
void clear() {front = tail = ;}
void ins(int id)
{
while (front<tail && a[id]*cmp>a[q[tail-]]*cmp) tail--;
q[tail++] = id;
}
void keep(int range)
{
while (front<tail && q[tail-]-q[front]>=range) front++;
}
int query(int id) { return q[id]; }
};Que q;
void input()
{
int i;
scanf("%d%d",&n,&k);
for ( i= ; i<=n ; i++ )
{
scanf("%d",&a[i]);
a[i+n] = a[i]; p[i] = i; p[i+n] = p[i];
}
for ( i= ; i<=*n ; i++ ) a[i] = a[i-]+a[i];
}
void solv()
{
int i,l,r,sum;
l = r = sum = -INF;
q.clear();
q.cmp = -;
for ( i= ; i<*n ; i++ )
{
q.ins(i);
q.keep(k);
if (a[i+]-a[q.query(q.front)] > sum)
{
l = p[q.query(q.front)]+;
r = p[i+];
sum = a[i+]-a[q.query(q.front)];
}else if (a[i+]-a[q.query(q.front)] == sum)
{
if (p[q.query(q.front)]+<l)
{
l = p[q.query(q.front)]+;
r = p[i+];
}else if (p[q.query(q.front)]+==l && p[i+]<r) r=p[i+];
}
}
printf("%d %d %d\n",sum,l,r);
}
int main()
{
int cas;
scanf("%d",&cas);
while (cas--)
{
input();
solv();
}
return ;
}
D(hdu 3401)
先列出朴素的dp方程逐渐,分析出可以优化的地方:
递推优化: dp[i][j] = max(dp[i][j],dp[i-1][j]);
单调队列优化: dp[i][j] = max{ dp[i][j] , dp[i-w-1][q.head]+(j-q.head)*num };
trick是前w+1天不能进行买卖,要特判并跳过买卖的决策.
#include <cmath>
#include <ctime>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 2020
#define INF 1000000000
int ap[maxn],bp[maxn],as[maxn],bs[maxn],t,maxp,w,dp[maxn][maxn];
void input()
{
int i;
scanf("%d%d%d",&t,&maxp,&w);
for ( i= ; i<=t ; i++ ) scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
}
int q[maxn],front,tail;
void DP()
{
int i,j,k;
for ( i=,dp[][]= ; i<=maxp ; i++ ) dp[][i] = -INF;
for ( i= ; i<=t ; i++ )
for ( j= ; j<=maxp ; j++ )
{
if (j<=as[i]) dp[i][j] = -ap[i]*j;
else dp[i][j] = -INF;
}
for ( i= ; i<=t ; i++ )
{
for ( j= ; j<=maxp ; j++ ) dp[i][j] = max(dp[i][j],dp[i-][j]);
if ((k=i-w-)<) continue; front = tail = ;
// buy
for ( j= ; j<=maxp ; j++ )
{
while (front<tail && j-q[front]>as[i]) front++;
while (front<tail && dp[k][j]+j*ap[i]>=dp[k][q[tail-]]+q[tail-]*ap[i]) tail--;
q[tail++] = j;
int tmp = dp[k][q[front]]-(j-q[front])*ap[i];
// printf("dp[%d][%d] = max: %d , dp[%d][%d]-(%d-%d)*%d = %d\n",i,j,dp[i][j],k,q[front],j,q[front],ap[i],max(dp[i][j],tmp));
dp[i][j] = max(dp[i][j],tmp);
} front = tail = ;
// sell
for ( j=maxp ; j>= ; j-- )
{
while (front<tail && q[front]-j>bs[i]) front++;
while (front<tail && dp[k][j]+j*bp[i]>=dp[k][q[tail-]]+q[tail-]*bp[i]) tail--;
q[tail++] = j;
int tmp = dp[k][q[front]]-(j-q[front])*bp[i];
// printf("dp[%d][%d] = max: %d , dp[%d][%d]-(%d-%d)*%d = %d\n",i,j,dp[i][j],k,q[front],j,q[front],bp[i],max(dp[i][j],tmp));
dp[i][j] = max(dp[i][j],tmp);
}
}
int ans=-INF;
for ( i= ; i<=t ; i++ )
for ( j= ; j<=maxp ; j++ ) ans = max(ans,dp[i][j]);
printf("%d\n",ans);
}
int main()
{
int cas;
scanf("%d",&cas);
while (cas--)
{
input();
DP();
}
return ;
}
E(hdu 3530)
关键是求区间给定区间的最大值和最小值,有很多办法,在此题中,可以用单调队列做到O(n).
trick: 当最大-最小>k时需要删除队列元素维护,但是当小于m时不用进行删除操作,因为没用。。。
#include <cmath>
#include <ctime>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1000100
int n,m,k,a[maxn];
int qs[maxn],ts,fs,ql[maxn],tl,fl,q[maxn],front,tail;
bool inq[maxn];
void input()
{
int i;
for ( i= ; i<=n ; i++ ) scanf("%d",&a[i]);
}
int queryl()
{
while (fl<tl && !inq[ql[fl]]) fl++;
return a[ql[fl]];
}
int querys()
{
while (fs<ts && !inq[qs[fs]]) fs++;
return a[qs[fs]];
}
void solv()
{
int i,ans=;
front = tail = fs = ts = fl = tl = ;
for ( i= ; i<=n ; i++ )
{
q[tail++] = i;
inq[i] = ;
while (fs<ts && a[i]<a[qs[ts-]]) ts--;
qs[ts++] = i;
while (fl<tl && a[i]>a[ql[tl-]]) tl--;
ql[tl++] = i;
while(front<tail && queryl()-querys()>k)
{
inq[q[front]] = ;
front++;
}
if (queryl()-querys()>=m && queryl()-querys()<=k) ans = max(ans,q[tail-]-q[front]+);
}
printf("%d\n",ans);
}
int main()
{
while (scanf("%d%d%d",&n,&m,&k)!=EOF)
{
input();
solv();
}
return ;
}
F(poj3017)
非常有启发性的一题:利用线段树的单点更新更新单调队列里面的值.单调队列保证了快速获得区间最值,线段树的区间查询保证了答案的最优性.
#include <cmath>
#include <ctime>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llong;
const llong INF = 1ll<<;
#define maxn 100100
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
struct node
{
int l,r,big;
};node q[maxn];
llong tree[maxn<<],m,dp[maxn];
int a[maxn],n,front,tail;
void buildtree(int l,int r,int rt)
{
tree[rt] = INF;
if (l == r) return;
buildtree(l,mid,ls);
buildtree(mid+,r,rs);
}
void pushup(int rt)
{
tree[rt] = min(tree[ls],tree[rs]);
}
void ins(llong var,int pos,int l,int r,int rt)
{
if (l == r)
{
tree[rt] = var;
return;
}
if (pos<=mid) ins(var,pos,l,mid,ls);
else ins(var,pos,mid+,r,rs);
pushup(rt);
}
llong query(int L,int R,int l,int r,int rt)
{
llong res1,res2;
res1 = res2 = INF;
if (L<=l && r<=R) return tree[rt];
if (L<=mid) res1 = query(L,R,l,mid,ls);
if (R>mid) res2 = query(L,R,mid+,r,rs);
return min(res1,res2);
}
llong solv()
{
int i,lft;
llong cnt=;
node tmp;
buildtree(,n,);
front = tail = ;
for ( i= ; i<=n ; i++ )
if (a[i]>m) return -;
for ( lft=i=,dp[]= ; i<=n ; i++ )
{
cnt += a[i];
while (cnt>m)
{
q[front].l++;
if (q[front].l>q[front].r)
{
ins(INF,front,,n,);
front++;
}else ins(dp[q[front].l-]+q[front].big,front,,n,);
cnt -= a[lft++];
}
tmp.l = tmp.r = i; tmp.big = a[i];
while (front<tail && tmp.big>=q[tail-].big)
{
tmp.l = q[tail-].l; //merge
ins(INF,tail-,,n,);
tail--;
}
q[tail++] = tmp;
ins(dp[q[tail-].l-]+q[tail-].big,tail-,,n,);
dp[i] = query(front,tail-,,n,);
// printf("dp[%d]=%I64d\n",i,dp[i]);
}
return dp[n];
}
int main()
{
while (scanf("%d%I64d",&n,&m)!=EOF)
{
for (int i= ; i<=n ; i++ ) scanf("%d",&a[i]);
printf("%I64d\n",solv());
}
return ;
}
G(poj3245)
为了满足 " 当p<q 时 , Bp > Aq " 的条件,需要先将数据预处理成块状, 即 对所有p ,要找到最大的q 使得 Bp <= Aq .
这是第一步,朴素做法O(n^2) , 用一点技巧可以做到nlogn : 线段树(比较麻烦,可能要离散化,代码量大) 或者 分别对A和对B降序排序O(nlogn) ,再用2个指针扫描 O(n) , 要记得记录排序前的原始下标.
第二步,在limt的限制下求最小sum的分组方法, 很容易想到要二分答案.
第三步,对于二分的sum值,需要一个验证办法.注意,让每组尽量接近sum的贪心分组办法是错的, 因为这里还要考虑到 ΣMi 的限制.
老老实实dp:
dp[i]表示以第i个为结尾, ΣM 最小的分组方法.
dp[i] = min {dp[j] + max{aj+1,...,ai} }.
这个方程和F题的非常相似,把决策存在单调队列里,用线段树得到最优值.
#include <cmath>
#include <ctime>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llong;
#define maxn 50100
#define ls (rt<<1)
#define rs ((rt<<1)+1)
#define mid ((l+r)>>1)
#define BIG 1
#define SML 0
#define INF (1ll<<31)
struct node
{
int a,b,id;
};node p[maxn],sa[maxn],sb[maxn],e[maxn];
llong init[];
llong sumb[maxn],tree[maxn<<];
int n,lmt,cnte,lst[maxn]; bool cmpa(const node& u,const node& v) { return u.a>v.a; }
bool cmpb(const node& u,const node& v) { return u.b>v.b; }
llong query_big(int L,int R,int l,int r,int rt)
{
llong resl,resr;
resl = resr = init[BIG];
if (L<=l && r<=R) return tree[rt];
if (L<=mid) resl = query_big(L,R,l,mid,ls);
if (R>mid) resr = query_big(L,R,mid+,r,rs);
return max(resl,resr);
}
llong query_sml(int L,int R,int l,int r,int rt)
{
llong resl,resr;
resl = resr = init[SML];
if (L<=l && r<=R) return tree[rt];
if (L<=mid) resl = query_sml(L,R,l,mid,ls);
if (R>mid) resr = query_sml(L,R,mid+,r,rs);
return min(resl,resr);
}
void buildtree(int l,int r,int rt,int flg)
{
tree[rt] = init[flg];
if (l==r) return;
buildtree(l,mid,ls,flg);
buildtree(mid+,r,rs,flg);
}
void pushup(int rt,int flg)
{
if (flg==BIG) tree[rt] = max(tree[ls],tree[rs]);
else tree[rt] = min(tree[rs],tree[ls]);
}
void ins(int val,int pos,int l,int r,int rt,int flg)
{
if (l==r) { tree[rt]=val; return; }
if (pos<=mid) ins(val,pos,l,mid,ls,flg);
else ins(val,pos,mid+,r,rs,flg);
pushup(rt,flg);
}
void pretreat()
{
int i,j,k;
buildtree(,n,,BIG);
for ( i= ;i<=n ; i++ ) sa[i]=p[i], sb[i]=p[i];
sort(sa+,sa++n,cmpa); sort(sb+,sb++n,cmpb);
// for ( i=1 ; i<=n ; i++ ) printf("sa: a=%d id=%d\nsb: b=%d id=%d\n\n",sa[i].a,sa[i].id,sb[i].b,sb[i].id);
for ( i=j=,k= ; i<=n ; i++ )
{
lst[ sb[i].id ] = sb[i].id;
while (j<=n && sa[j].a>=sb[i].b) k=max(k,sa[j].id),j++;
lst[ sb[i].id ] = max(sb[i].id,k);
ins(lst[ sb[i].id ],sb[i].id,,n,,BIG);
}
for ( i= ; i<=n ; i++ )
lst[i] = query_big(i,lst[i],,n,);
buildtree(,n,,BIG);
for ( i= ; i<=n ; i++ ) sumb[i] = sumb[i-] + p[i].b;
for ( i= ; i<=n ; i++ ) ins(p[i].a,i,,n,,BIG);
for ( i=,cnte= ; i<=n ; i++ )
{
e[++cnte].a = query_big(i,lst[i],,n,);
e[cnte].b = sumb[lst[i]] - sumb[i-];
e[cnte].id = cnte;
i = lst[i];
}
// for ( i=1 ; i<=cnte ; i++ ) printf("e[%d]: a=%d b=%d\n",i,e[i].a,e[i].b);
for ( i= ; i<=cnte ; i++ ) sumb[i] = sumb[i-] + e[i].b;
}
struct node2
{
int l,r,big;
};node2 q[maxn]; int front,tail;
llong dp[maxn];
int check(int sum)
{
int i,lft;
llong cnt=;
node2 tmp; front = tail = ;
for ( i= ; i<=cnte ; i++ ) if (e[i].b>sum) return ; for ( i=lft= ; i<=cnte ; i++ )
{
cnt += e[i].b;
while (cnt>sum)
{
q[front].l++;
if (q[front].l>q[front].r)
{
ins(init[SML],front,,n,,SML);
front++;
}else ins(dp[q[front].l-]+q[front].big,front,,n,,SML);
cnt -= e[lft++].b;
}
tmp.l = tmp.r = i; tmp.big = e[i].a;
while (front<tail && tmp.big>=q[tail-].big)
{
tmp.l = q[tail-].l;
ins(init[SML],tail-,,n,,SML);
tail--;
}
q[tail++] = tmp;
ins(dp[tmp.l-]+tmp.big,tail-,,n,,SML);
dp[i] = query_sml(front,tail-,,n,);
}
if (dp[cnte]<=lmt) return ;
else return ;
}
int solv()
{
int l,r;
l = ; r = sumb[n];
while (l<r)
{
if (check(mid)) r=mid;
else l=mid+;
} return r;
}
int main()
{
init[BIG] = ; init[SML] = INF;
scanf("%d%d",&n,&lmt);
for (int i= ; i<=n ; i++ ) { scanf("%d%d",&p[i].a,&p[i].b); p[i].id=i; }
pretreat();
int ans = solv();
printf("%d\n",ans);
return ;
}
斜率优化dp：
H(hdu 2993)
#include <cmath>
#include <ctime>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llong;
#define maxn 100100
#define ls (rt<<1)
#define rs ((rt<<1)+1)
#define mid ((l+r)<<1)
int sum[maxn];
int n,m;
int q[maxn],front,tail; double g(int a,int b)
{
double res = (double)(sum[b]-sum[a-])/(double)(b-a+1.0);
return res;
}
void solv()
{
int i;
double ans=;
front = tail = ;
for ( i=m ; i<=n ; i++ )
{
while (front+<tail && g(q[tail-],q[tail-])>g(q[tail-],i-m+)) tail--;
q[tail++] = i-m+;
while (front+<tail && g(q[front],i)<=g(q[front+],i)) front++;
ans = max(ans,g(q[front],i));
}
printf("%.2lf\n",ans);
}
int GetInt()
{
char ch=getchar();
while(ch<''||ch>'')ch=getchar();
int num=;
while(ch>=''&&ch<=''){
num=num*+ch-'';
ch=getchar();
}
return num;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
for (int i= ; i<=n ; i++ )
{
sum[i] = GetInt();
sum[i] += sum[i-];
}
solv();
}
return ;
}
I(hdu 2829)
#include <cmath>
#include <ctime>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 1010
typedef long long llong;
#define ls (rt<<1)
#define rs ((rt<<1)+1)
#define mid ((l+r)<<1)
const llong INF = 1ll<<;
llong dp[maxn][maxn],v[maxn],sum[maxn];
int n,m,a[maxn]; void init()
{
int i;
for ( i= ; i<=n ; i++ ) sum[i] = sum[i-]+a[i];
for ( i= ; i<=n ; i++ ) v[i] = v[i-]+sum[i-]*a[i];
}
int q[maxn],front,tail; llong w(int j,int i)
{
return v[i]-v[j]-sum[j]*(sum[i]-sum[j]);
}
int x;
double g(int id,int a,int b)
{
double xa,xb,ya,yb;
ya = dp[id][a] - v[a]+sum[a]*sum[a]; xa = sum[a];
yb = dp[id][b] - v[b]+sum[b]*sum[b]; xb = sum[b];
return (ya-yb) / (xa-xb);
}
void DP()
{
int i,j;
for ( i= ; i<=n ; i++ ) dp[][i] = v[i];
// for ( i=0 ; i<=n ; i++ ) printf("dp[0][%d]=%I64d\n",i,dp[0][i]); printf("\n"); for ( i= ; i<=m ; i++ )
{
front = tail = ;
q[tail++] = i;
for ( j=i+ ; j<=n ; j++ )
{
x = j;
while (front+<tail && g(i-,q[front],q[front+])<=(double)sum[j]) front++;
dp[i][j] = dp[i-][q[front]] + w(q[front],j);
// printf("dp[%d][%d] = %I64d q[front]=%d\n",i,j,dp[i][j],q[front]);
while (front+<tail && g(i-,q[tail-],q[tail-])>=g(i-,q[tail-],j)) tail--;
q[tail++] = j;
}
}
llong res=INF;
for ( i= ; i<=m ; i++ ) res = min(res,dp[i][n]);
cout<<res<<endl;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
if (!n && !m) break;
for (int i= ; i<=n ; i++ ) scanf("%d",&a[i]);
init();
DP();
}
return ;
}
J(hdu 3507)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long llong;
#define maxn 600010
llong dp[maxn],sum[maxn];
int a[maxn],n,m,q[maxn],front,tail; double dx(int a,int b){return (double)(sum[a]-sum[b]);}
double dy(int a,int b){return (double)(dp[a]+sum[a]*sum[a]-dp[b]-sum[b]*sum[b]);}
int check(int a,int b,llong c)
{
llong resa = dp[a] + (sum[a]-c)*(sum[a]-c);
llong resb = dp[b] + (sum[b]-c)*(sum[b]-c);
if (resa>resb) return ;
else return ;
}
void solv()
{
int i;
for ( i= ; i<=n ; i++ ) sum[i] = sum[i-] + a[i];
front = tail = ;
q[tail++] = ;
for ( i= ; i<=n ; i++ )
{
while (front+<tail && check(q[front],q[front+],sum[i])) front++;
dp[i] = dp[q[front]] + (sum[i]-sum[q[front]]) * (sum[i]-sum[q[front]])+m;
// printf("dp[%d] = %lld\n",i,dp[i]);
while (front+<tail && dy(q[tail-],q[tail-]) * dx(i,q[tail-]) >= dx(q[tail-],q[tail-]) * dy(i,q[tail-])) tail--;
q[tail++] = i;
}
cout<<dp[n]<<endl;
}
int main()
{
while (scanf("%d%d",&n,&m)!=EOF)
{
for (int i= ; i<=n ; i++ ) scanf("%d",&a[i]);
solv();
}
return ;
}
I,J需要比较决策得到斜率形式,比较决策的形式:
i<j<k 时 g(i,j)<常数c可推出j更优 ,g(i,j)<g(j,k)<常数c 可推出决策j不会为最优可从集合中去掉
H不需要比较决策直接是斜率形式.
设i<j<k , g(i,j)>g(j,k) 可以通过图像知道上凸点j不会成为最优决策.