六 01

NOI 2005 瑰丽华尔兹

NOI Add comments359 views

这是一个需要用单调队列优化的动态规划问题。根据数据规模的提示，要想过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)。

?View Code CPP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

/* 
 * 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;
}

瑰丽华尔兹

【任务描述】

你跳过华尔兹吗？当音乐响起，当你随着旋律滑动舞步，是不是有一种漫步仙境的惬意？众所周知，跳华尔兹时，最重要的是有好的音乐。但是很少有几个人知道，世界上最伟大的钢琴家一生都漂泊在大海上，他的名字叫丹尼?布德曼?T.D.?柠檬?1900，朋友们都叫他1900。

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

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

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

这是一个风雨交加的夜晚，海风卷起层层巨浪拍打着弗吉尼亚号，邮轮随着巨浪剧烈的摇摆。船上的新萨克斯手迈克斯?托尼晕船了，1900将他 邀请到舞厅，然后——，然后松开了固定钢琴的闸，于是，钢琴随着海轮的倾斜滑动起来。准确的说，我们的主角1900、钢琴、邮轮随着1900的旋律一起跳 起了华尔兹，所有的事物好像都化为一体，随着“强弱弱”的节奏，托尼的晕船症也奇迹般地一点一点恢复。正如托尼在回忆录上这样写道：

大海摇晃着我们
使我们转来转去
快速的掠过灯和家具
我意识到我们正在和大海一起跳舞
真是完美而疯狂的舞者

晚上在金色的地板上快乐的跳着华尔兹是不是很惬意呢？也许，我们忘记了一个人，那就是艾米丽，她可没闲着：她必须在适当的时候施魔法帮助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

【样例说明】

钢琴的滑行路线：

Image:Adv1900.png

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

【评分方法】

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

【数据范围】

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

Maybe you like

标签：, ,


Leave a Reply

38 queries. 0.612 seconds. Designed by NattyWP .
Images by desEXign.