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

DP优化之斜率优化

代码

#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

【样例说明】

钢琴的滑行路线：

钢琴在“×”位置上时天使使用一次魔法，因此滑动总长度为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

样例输出

17

代码

#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 ;
}