现在的位置: 首页 > 综合 > 正文

DP优化之单调队列专题

2013年06月12日 ⁄ 综合 ⁄ 共 5947字 ⁄ 字号小中大 ⁄ 评论关闭

单调队列和之前之前的斜率优化有很大的交集。

DP优化之斜率优化

具体看wyn神牛的1D/1D动归优化。

Sliding window1

给你一个长度为N的数组，一个长为K的滑动的窗体从最左移至最右端，你只能见到窗口的K个数，每次窗体向右移动一位，如下表：

Window position	Min value	Max value
[ 1 3 -1 ] -3 5 3 6 7	-1	3
1 [ 3 -1 -3 ] 5 3 6 7	-3	3
1 3 [ -1 -3 5 ] 3 6 7	-3	5
1 3 -1 [ -3 5 3 ] 6 7	-3	5
1 3 -1 -3 [ 5 3 6 ] 7	3	6
1 3 -1 -3 5 [ 3 6 7 ]	3	7

你的任务是找出窗口在各位置时的maxvalue,min value.

输入格式：

第1行n,k,第2行为长度为n的数组

输出格式：

2行，第1行每个位置的min value,第2行每个位置的max value

样例：

window.in

8 3

1 3 -1 -3 5 3 6 7

window.out

-1 -3 -3 -3 3 3

3 3 5 5 6 7

数据范围：

20%： n<=500;50%: n<=100000;

100%: n<=1000000;

水题一道。。。。

代码

#include<iostream>
#include<cstdio>
#define N 2000000
using namespace std;

int pos[N],Q[N],x[N];
int n,len,l,r;
int main()
{
freopen("window.in","r",stdin);
freopen("window.out","w",stdout);
scanf("%d%d",&n,&len);
for (int i=1;i<=n;++i) scanf("%d",&x[i]);

Q[1]=x[1];l=1;r=1;pos[1]=1;
for (int i=2;i<=n;++i)
{
while (l<=r && pos[l]<i-len+1) ++l;
while (r>=l && x[i]<Q[r]) --r;
++r;Q[r]=x[i];pos[r]=i;
if (i>=len)
printf("%d ",Q[l]);
}
printf("\n");
Q[1]=x[1];l=1;r=1;pos[1]=1;
for (int i=2;i<=n;++i)
{
while (l<=r && pos[l]<i-len+1) ++l;
while (r>=l && x[i]>Q[r]) --r;
++r;Q[r]=x[i];pos[r]=i;
if (i>=len)
printf("%d ",Q[l]);
}
printf("\n");
return 0;
}

瑰丽华尔兹

【任务描述】

你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？

众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼·布德曼·T.D.·柠檬·1900，朋友们都叫他1900。

1900在20世纪的第一年出生在往返于欧美的邮轮弗吉尼亚号上，很不幸他刚出生就被抛弃了，成了孤儿。1900孤独的成长在弗吉尼亚号上，从未离开过这个摇晃的世界。也许是对他命运的补偿，上帝派可爱的小天使艾米丽照顾他。

可能是天使的点化，1900拥有不可思议的钢琴天赋：从未有人教，从没看过乐谱，但他却能凭着自己的感觉弹出最沁人心脾的旋律。当1900的音乐获得邮轮上所有人的欢迎时，他才8岁，而此时的他已经乘着海轮往返欧美大陆50余次了。

虽说是钢琴奇才，但1900还是个孩子，他有着和一般男孩一样的好奇和调皮，只不过更多一层浪漫的色彩罢了：

这是一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手马克斯·托尼晕船了，1900招呼托尼和他一起坐上舞厅里的钢琴，然后松开了固定钢琴的闸，于是，钢琴随着海轮的倾斜滑动起来。准确的说，我们的主角1900、钢琴、邮轮随着1900的旋律一起跳起了华尔兹，随着“嘣嚓嚓”的节奏，托尼的晕船症也奇迹般的消失了。后来托尼在回忆录上写道：

大海摇晃着我们

使我们转来转去

快速的掠过灯和家具

我意识到我们正在和大海一起跳舞

真是完美而疯狂的舞者

晚上在金色的地板上快乐的跳着华尔兹是不是很惬意呢？也许，我们忘记了一个人，那就是艾米丽，她可没闲着：她必须在适当的时候施展魔法帮助1900，不让钢琴碰上舞厅里的家具。

不妨认为舞厅是一个N行M列的矩阵，矩阵中的某些方格上堆放了一些家具，其他的则是空地。钢琴可以在空地上滑动，但不能撞上家具或滑出舞厅，否则会损坏钢琴和家具，引来难缠的船长。

每个时刻，钢琴都会随着船体倾斜的方向向相邻的方格滑动一格，相邻的方格可以是向东、向西、向南或向北的。而艾米丽可以选择施魔法或不施魔法：如果不施魔法，则钢琴会滑动；如果施魔法，则钢琴会原地不动。

艾米丽是个天使，她知道每段时间的船体的倾斜情况。她想使钢琴在舞厅里滑行路程尽量长，这样1900会非常高兴，同时也有利于治疗托尼的晕船。但艾米丽还太小，不会算，所以希望你能帮助她。

【输入格式】

输入文件的第一行包含5个数N, M, x,y和K。N和M描述舞厅的大小，x和y为钢琴的初始位置（x行y列）；我们对船体倾斜情况是按时间的区间来描述的，且从1开始计量时间，比如“在[1, 3]时间里向东倾斜，[4, 5]时间里向北倾斜”，因此这里的K表示区间的数目。

以下N行，每行M个字符，描述舞厅里的家具。第i行第j列的字符若为‘ .’，则表示该位置是空地；若为‘ x ’，则表示有家具。

以下K行，顺序描述K个时间区间，格式为：s_i t_i d_i。表示在时间区间[s_i, t_i]内，船体都是向d_i方向倾斜的。d_i为1, 2, 3, 4中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）。输入保证区间是连续的，即

s₁ = 1

s_i = t_i_-1 + 1 (1 < i ≤ K)

t_K = T

【输出格式】

输出文件仅有1行，包含一个整数，表示钢琴滑行的最长距离(即格子数)。

【输入样例】

4 5 4 1 3

..xx.

.....

...x.

.....

1 3 4

4 5 1

6 7 3

【输出样例】

【样例说明】

钢琴的滑行路线：

钢琴在“×”位置上时天使使用一次魔法，因此滑动总长度为6。

【评分方法】

本题没有部分分，你的程序的输出只有和我们的答案完全一致才能获得满分，否则不得分。

【数据范围】

50%的数据中，1≤N, M≤200，T≤200；

100%的数据中，1≤N, M≤200，K≤200，T≤40000。

代码

#include<iostream>
#include<cstdio>
#define INF 10000000
using namespace std;

int f[201][201][201];
int Q[2000],pos[2000],l,r,n,m,k,sx,sy,si,ti,dir,ans;
char map[201][201];
void solve1(int x)
{
for (int j=0;j<m;++j)
{
l=1;r=0;
for (int i=n-1;i>=0;--i)
{
while (l<=r && pos[l]-i>ti) ++l;
if (map[i][j]=='x') {l=1;r=0;continue;} //clear queue;

if (l<=r && Q[l]-i>f[x+1][i][j]) f[x+1][i][j]=Q[l]-i;

if (f[x][i][j]!=-INF)
{
while (r>=l && f[x][i][j]+i>=Q[r]) --r;
++r;Q[r]=f[x][i][j]+i;pos[r]=i;
}
}
}
}
void solve2(int x)
{
for (int j=0;j<m;++j)
{
l=1;r=0;
for (int i=0;i<n;++i)
{
while (l<=r && i-pos[l]>ti) ++l;
if (map[i][j]=='x') {l=1;r=0;continue;} //clear queue;

if (l<=r && Q[l]+i>f[x+1][i][j]) f[x+1][i][j]=Q[l]+i;

if (f[x][i][j]!=-INF)
{
while (r>=l && f[x][i][j]-i>=Q[r]) --r;
++r;Q[r]=f[x][i][j]-i;pos[r]=i;
}
}
}
}
void solve3(int x)
{
for (int i=0;i<n;++i)
{
l=1;r=0;
for (int j=m-1;j>=0;--j)
{
while (l<=r && pos[l]-j>ti) ++l;
if (map[i][j]=='x') {l=1;r=0;continue;} //clear queue;

if (l<=r && Q[l]-j>f[x+1][i][j]) f[x+1][i][j]=Q[l]-j;

if (f[x][i][j]!=-INF)
{
while (r>=l && f[x][i][j]+j>=Q[r]) --r;
++r;Q[r]=f[x][i][j]+j;pos[r]=j;
}
}
}
}
void solve4(int x)
{
for (int i=0;i<n;++i)
{
l=1;r=0;
for (int j=0;j<m;++j)
{
while (l<=r && j-pos[l]>ti) ++l;
if (map[i][j]=='x') {l=1;r=0;continue;} //clear queue;

if (l<=r && Q[l]+j>f[x+1][i][j]) f[x+1][i][j]=Q[l]+j;

if (f[x][i][j]!=-INF)
{
while (r>=l && f[x][i][j]-j>=Q[r]) --r;
++r;Q[r]=f[x][i][j]-j;pos[r]=j;
}
}
}
}
int main()
{
freopen("adv1900.in","r",stdin);
freopen("adv1900.out","w",stdout);
scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);
for (int i=0;i<n;++i) scanf("%s",&map[i]);
for (int x=0;x<=k;++x)
for (int i=0;i<n;++i) for (int j=0;j<m;++j) f[x][i][j]=-INF;
f[0][sx-1][sy-1]=0;
for (int i=0;i<k;++i)
{
scanf("%d%d%d",&si,&ti,&dir);ti=ti-si+1;
for (int x=0;x<n;++x)
for (int y=0;y<m;++y) f[i+1][x][y]=f[i][x][y];
if (dir==1) solve1(i);
if (dir==2) solve2(i);
if (dir==3) solve3(i);
if (dir==4) solve4(i);
/* printf("------------\n");
for (int x=0;x<n;++x)
for (int y=0;y<m;++y)
printf("%d %d %d\n",x,y,f[i+1][x][y]);
printf("-------------\n"); */

}
ans=-INF;
for (int i=0;i<n;++i) for (int j=0;j<m;++j)
if (f[k][i][j]>ans) ans=f[k][i][j];
cout<<ans<<endl;
return 0;
}

货币兑换（BOI2003）

你每天会收到一些货币A，可能正也可能负，银行允许你在某天将手头所有的货币A兑换成B。第i天的兑换比率是1 A ：i B，同时你必须再多付出t B被银行收取。在N天你必须兑换所有持有的货币A。

任务

找一个方案使第N天结束时能得到最多的货币B

输入文件(.in)

第一行是整数N,T

第二行是N个整数Ai，表示第i天开始时得到Ai的A币

输出文件(euro.out)

将最终得到的最多的B货币数写到文件

数据范围

1 ≤ N ≤ 34 567
0 ≤ T ≤ 34 567

样例输入

7 1

-10 3 -2 4 –6 2 3

样例输出

代码

#include<iostream>
#include<cstdio>
#define N 200000

#define LL long long
using namespace std;
LL INF=999999*9999999;
LL S[N],pos[N],c[N],vis[N],sum[N],f[N];
LL n,t,l,r,ans,tot;
LL Bigger(LL x,LL y)
{
LL l,r,mid;
l=S[x];r=n;
while (l<r)
{
mid=(l+r)/2;
if (f[x]+(sum[mid]-sum[x])*mid-t>f[y]+(sum[mid]-sum[y])*mid-t)
l=mid+1; else r=mid;
}
if ( f[x]+(sum[l]-sum[x])*l-t>f[y]+(sum[l]-sum[y])*l-t ) return INF;
else return l;
}
int main()
{
freopen("euro.in","r",stdin);
freopen("euro.out","w",stdout);
scanf("%I64d%I64d",&n,&t);
for (LL i=1;i<=n;++i) scanf("%I64d",&c[i]),sum[i]=sum[i-1]+c[i];

S[1]=1;pos[1]=0;tot=0;l=1;r=1;vis[0]=1;

for (LL i=1;i<=n;++i)
{
tot+=c[i];
if (tot>=0) continue;

vis[i]=1;
while (l<r && i>=S[l+1]) ++l;
if (S[l]<i) S[l]=i;

f[i]=f[pos[l]]+(sum[i]-sum[pos[l]])*i-t;

while (l<=r && Bigger(pos[r],i)<=S[r] ) --r;
++r;
if (l==r)
{
S[r]=i+1;
pos[r]=i;
}
else
{
S[r]=Bigger(pos[r-1],i);
pos[r]=i;
}
tot=0;

}
// for (LL i=1;i<=n;++i) printf("%I64d %I64d\n",i,f[i]+(sum[n]-sum[i])*n-t);
// ans=0;
// for (int i=1;i<=n;++i) ans+=c[i]*i;
// cout<<ans<<endl;
ans= (LL) (-999999999)*99999999; //cout<<ans<<endl;
for (LL i=0;i<=n;++i) if (vis[i])
if (f[i]+(sum[n]-sum[i])*n-t>ans) ans=f[i]+(sum[n]-sum[i])*n-t;
cout<<ans<<endl;
return 0;
}

【上篇】关于 bootloader 里的物理地址到虚拟地址的影射
【下篇】用 Ajax 和 Persevere 将 JavaScript 对象映射到服务器数据

作者: mumu11andl

该日志由 mumu11andl 于11年前发表在综合分类下，最后更新于 2013年06月12日.
转载请注明: DP优化之单调队列专题 | 学步园 +复制链接

抱歉!评论已关闭.

学步园

DP优化之单调队列专题

DP优化之斜率优化

瑰丽华尔兹

【任务描述】

【输入格式】

【输出格式】

【输入样例】

【输出样例】

【样例说明】

【评分方法】

【数据范围】

作者: mumu11andl

书签

最新文章New

本站推荐

返回首页

学步园

DP优化之单调队列 专题

DP优化之斜率优化

瑰丽华尔兹

【任务描述】

【输入格式】

【输出格式】

【输入样例】

【输出样例】

【样例说明】

【评分方法】

【数据范围】

作者: mumu11andl

书签

最新文章New

本站推荐

返回首页

DP优化之单调队列专题