本文正體字版由OpenCC轉換

這是一個需要用單調隊列優化的動態規劃問題。根據數據規模的提示，要想過100%就不能把時間作爲一個狀態量表示，而以時間區間。

於是我們寫出狀態 F[p][i][j]表示第i個時間區間末的時刻，鋼琴在(i,j)位置的最長滑行路程。狀態轉移方程就是

F[p][i][j] = Max { F[p-1][i’][j’] + dist((i,j),(i’,j’)) }  爲在第p個時間區間內能從(i’,j’)到(i,j)的位置

這個狀態轉移方程的時間複雜度是O(NMT)的，只能過50％的數據，所以要優化狀態轉移。由於只能直線滑動，所以每次狀態轉移都是線性的，取一個最大值。我們可以想辦法加快取最大值的速度，單調隊列！

定義當前時間爲該狀態是第幾個被計算的，假設第p個時間區間方向爲1（從下向上滑），要從下向上遞推，最下面的狀態時間就是0，往上一格時間增加1。對於狀態F[p][i][j]，如果(i,j)處沒有障礙，把(F[p-1][i][j] － 當前時間)加入單調隊列，然後在單調隊列中取出合法最大值，再加上當前時間的值賦給F[p][i][j]。如果(i,j)處是障礙，則F[p][i][j]賦爲一個無效值，然後清空單調隊列。

這樣經過優化的決策時間就是均攤O(1)的，所以時間複雜度爲O(NMK)。

/* 
 * Problem: NOI2005 adv1900
 * Author: Guo Jiabao
 * Time: 2009.6.1 11:03
 * State: Solved
 * Memo: 動態規劃
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=202,MAXK=201,INF=0x7FFFFFF;
struct MonoList
{
	int A[MAXN],T[MAXN];
	int head,tail;
	void clear()
	{
		head=0;tail=-1;
	}
	void ins(int t,int v)
	{
		tail++;
		T[tail]=t; A[tail]=v;
		while (tail-1 >= head && A[tail] > A[tail-1])
		{
			A[tail-1]=A[tail];
			T[tail-1]=T[tail];
			tail--;
		}
	}
	int get(int thistime,int timelimit)
	{
		while (head+1 <=tail && (thistime - T[head] > timelimit) )
			head++;
		return A[head];
	}
}Mono;
struct timeseg
{
	int s,t,d;
}T[MAXK];
bool forbid[MAXN][MAXN];
int N,M,K,Ans;
int F[2][MAXN][MAXN];

void init()
{
	int i,j,x,y,c;
	freopen("adv1900.in","r",stdin);
	freopen("adv1900.out","w",stdout);
	scanf("%d%d%d%d%d",&N,&M,&x,&y,&K);
	for (i=1;i<=N;i++)
	{
		do c=getchar(); while (c==10||c==13); ungetc(c,stdin);
		for (j=1;j<=M;j++)
		{
			c=getchar();
			forbid[i][j]=c=='x';
			F[0][i][j]=-INF;
		}
	}
	F[0][x][y]=Ans=0;
	for (i=1;i<=K;i++)
	{
		scanf("%d%d%d",&T[i].s,&T[i].t,&T[i].d);
		T[i].t-=T[i].s-1;
	}
}
void update(int thistime,int p,int i,int j,int y)
{
	int q=!p;
	if (forbid[i][j])
	{
		F[p][i][j]=-INF;
		Mono.clear();
		return;
	}
	Mono.ins(thistime,F[q][i][j] - thistime);
	F[p][i][j] = Mono.get(thistime,T[y].t) + thistime;
	if (F[p][i][j] > Ans)
		Ans = F[p][i][j];
}
void dynamic()
{
	int y,p,i,j,thistime;
	for (y=p=1;y<=K;y++,p=!p)
	{
		if (T[y].d==1)
		{
			for (j=1;j<=M;j++)
			{
				Mono.clear();
				for (i=N;i>=1;i--)
					update(N-i,p,i,j,y);
			}
		}
		else if(T[y].d==2)
		{
			for (j=1;j<=M;j++)
			{
				Mono.clear();
				for (i=1;i<=N;i++)
					update(i-1,p,i,j,y);
			}
		}
		else if (T[y].d==3)
		{
			for (i=1;i<=N;i++)
			{
				Mono.clear();
				for (j=M;j>=1;j--)
					update(M-j,p,i,j,y);
			}
		}
		else
		{
			for (i=1;i<=N;i++)
			{
				Mono.clear();
				for (j=1;j<=M;j++)
					update(j-1,p,i,j,y);
			}
		}
	}
}
int main()
{
	init();
	dynamic();
	printf("%d\n",Ans);
	return 0;
}

<h2><span class="mw-headline">瑰麗華爾茲 </span></h2>

【任務描述】

你跳過華爾茲嗎？當音樂響起，當你隨着旋律滑動舞步，是不是有一種漫步仙境的愜意？衆所周知，跳華爾茲時，最重要的是有好的音樂。但是很少有幾個人知道，世界上最偉大的鋼琴家一生都漂泊在大海上，他的名字叫丹尼?佈德曼?T.D.?檸檬?1900，朋友們都叫他1900。

1900出生於20世紀的第一年出生在往返於歐美的郵輪弗吉尼亞號上，然後就被拋棄了。1900剛出生就成了孤兒，孤獨的成長在弗吉尼亞號上，從未離開過這個搖晃的世界；也許是對他命運的補償，上帝派可愛的小天使艾米麗照顧他。

可能是天使的點化，1900擁有不可思議的鋼琴天賦，從未有人教，從沒看過樂譜，但他卻能憑着自己的感覺彈出最沁人心脾的旋律。當1900的音樂獲得郵輪上所有人的歡迎時，他才8歲，而此時他已經乘着海輪往返歐美50多次了。

雖說是鋼琴奇才，但1900還是個8歲的孩子，他有着和一般男孩一樣的好奇的調皮，不過可能更有一層浪漫的色彩罷了：

這是一個風雨交加的夜晚，海風捲起層層巨浪拍打着弗吉尼亞號，郵輪隨着巨浪劇烈的搖擺。船上的新薩克斯手邁克斯?託尼暈船了，1900將他 邀請到舞廳，然後——，然後鬆開了固定鋼琴的閘，於是，鋼琴隨着海輪的傾斜滑動起來。準確的說，我們的主角1900、鋼琴、郵輪隨着1900的旋律一起跳 起了華爾茲，所有的事物好像都化爲一體，隨着“強弱弱”的節奏，託尼的暈船症也奇蹟般地一點一點恢復。正如託尼在回憶錄上這樣寫道：
<pre>大海搖晃着我們
使我們轉來轉去
快速的掠過燈和傢俱
我意識到我們正在和大海一起跳舞
真是完美而瘋狂的舞者</pre>
晚上在金色的地板上快樂的跳着華爾茲是不是很愜意呢？也許，我們忘記了一個人，那就是艾米麗，她可沒閒着：她必須在適當的時候施魔法幫助1900，不讓鋼琴碰上舞廳裏的傢俱。而艾米麗還小，她無法施展魔法改變鋼琴的運動方向或速度，而只能讓鋼琴停一下。

不妨認爲舞廳是一個N行M列的矩陣，矩陣中的某些方格上堆放了一些傢俱，其他的則是空地。鋼琴可以在空地上滑動，但不能撞上傢俱或滑出舞廳，否則會損壞鋼琴和傢俱，引來難纏的船長。

每個時刻，鋼琴都會隨着船體傾斜的方向向相鄰的方格滑動一格，其中相鄰的方格可以是向東、向西、向南或向北的。而艾米麗可以選擇施魔法或不施魔法，如果不施魔法，則鋼琴會滑動，而如果施魔法，則鋼琴會原地不動。 艾米麗是個天使，她知道每段時間的船體的傾斜情況。她想使鋼琴儘量長時間在舞廳裏滑行，這樣1900會非常高興，同時也有利於治療託尼的暈船。但艾米麗還太小，不會算，所以希望你能幫助她。

【輸入格式】

輸入文件的第一行包含5個數N, M, x, y和K。N和M描述舞廳的大小，x和y爲在第1時刻初鋼琴的位置（x行y列）；我們對船體傾斜情況是按時間的區間來描述的，比如“在[1, 3]時間裏向東傾斜，[4, 5]時間裏向北傾斜”，因此這裏的K表示區間的數目。

以下N行，每行M個字符，描述舞廳裏的傢俱。第i行第j列的字符若爲‘ . '，則表示該位置是空地；若爲‘ x '，則表示有傢俱。

以下K行，順序描述K個時間區間，格式爲：si ti di(1 ≤ i ≤ K)。表示在時間區間[si, ti]內，船體都是向di方向傾斜的。di爲1, 2, 3, 4中的一個，依次表示北、南、西、東（分別對應矩陣中的上、下、左、右）。輸入保證區間是連續的，即

• s1 = 1

• ti = si-1 + 1 (1 < i ≤ K)

• tK = T

  【輸出格式】

  輸出文件僅有1行，包含一個整數，表示鋼琴滑行的最長距離(即格子數)。

  【輸入樣例】

  4 5 4 1 3
    ..xx.
    .....
    ...x.
    .....
    1 3 4
    4 5 1
    6 7 2

  【輸出樣例】

  6

  【樣例說明】

  鋼琴的滑行路線：

  

  鋼琴在“×位置上時天使使用一次魔法，因此滑動總長度爲6。

  【評分方法】

  本題沒有部分分，你的程序的輸出只有和我們的答案完全一致才能獲得滿分，否則不得分。

  【數據範圍】

• 50%的數據中，1≤N, M≤200，T≤200；

• 100%的數據中，1≤N, M≤200，K≤200，T≤40000。

上次修改時間 2017-05-22