NOI 2005ビューティワルツ(DP+単調キュー)
1499:[NOI 2005]きらびやかなワルツ
Time Limit: 3 Sec
Memory Limit: 64 MB
Submit: 490
Solved: 250
[ Submit][ Status][ Discuss]
Description
ワルツを飛び越えたの?音楽が鳴ると、メロディーに合わせて滑って踊ると、仙境を歩く快適さがありますか?よく知られているように、ワルツを踊るとき、最も重要なのは良い音楽があることです.しかし、世界で最も偉大なピアニストが一生海に漂泊していることを知っている人は少ない.彼の名前はダニー・ブドマン・T.D.レモン・1900で、友达は1900と呼んでいる.1900年、20世紀の初年に欧米を往復するクルーズ船バージニア号に生まれたが、不幸にも生まれたばかりで捨てられ、孤児になった.1900年の孤独な成長はバージニア号で、この揺れる世界を離れたことがない.彼の運命の補償かもしれないが、神はかわいい天使エミリーを世話してくれた.天使の点化かもしれませんが、1900は不思議なピアノの才能を持っています.誰も教えていません.楽譜を見たことがありませんが、彼は自分の感覚で最も人の心に沁みるメロディーを弾くことができます.1900年の音楽がクルーズ船のすべての人に歓迎された時、彼はまだ8歳で、この時の彼はすでにクルーズ船に乗って欧米大陸を50回以上往復した.ピアノの奇才とはいえ、1900年はまだ子供で、彼は普通の男の子と同じ好奇心といたずらを持っていて、ただもっとロマンチックな色にすぎない.これは風雨が入り交じった夜で、海風が波を巻いてバージニア号をたたき、クルーズ船は波とともに激しく揺れている.船の新しいサックスのマックス・トニーは船酔いし、1900年にトニーにダンスホールのピアノに乗るように呼びかけ、ピアノを固定するブレーキを緩めた.すると、ピアノは海輪の傾斜に従って滑った.正確に言えば、私たちの主役1900、ピアノ、クルーズ船は1900のメロディーとともにワルツを踊り、「パチパチ」のリズムとともにトニーの船酔い症も奇跡的に消えた.それからトニーは回顧録で、海が揺れて私たちを回転させて急速に明かりと家具をかすめて、私たちが海と一緒に踊っていることに気づいた.本当に完璧でクレイジーなダンサーが夜、金色の床でワルツを楽しく踊っているのは快適ではないかと書いた.もしかすると、私たちは一人を忘れたかもしれません.それはエミリーです.彼女は暇ではありません.彼女は適当な時に魔法をかけて1900を助けなければなりません.ピアノがダンスホールの家具にぶつからないようにしなければなりません.ダンスホールはN行M列の行列であり、行列の中のいくつかの四角い格子に家具が積み上げられており、他は空き地であると考えてもいい.ピアノは空き地で滑ることができますが、家具にぶつかったり、ダンスホールを滑ったりしてはいけません.そうしないと、ピアノや家具を壊して、付きまとう船長を引き起こします.各時刻、ピアノは船体の傾斜方向に従って隣接する四角い格子にスライドし、隣接する四角い格子は東、西、南または北にスライドすることができる.エミリーは魔法をかけるか、魔法をかけないかを選ぶことができます.魔法をかけなければ、ピアノは滑ります.魔法をかけるとピアノは動かない.エミリーは天使で、彼女は時間ごとに船体の傾斜状況を知っています.彼女はピアノをダンスホールでできるだけ長く滑らせたいと思っています.1900年はとても喜んで、トニーの船酔いの治療にも役立ちます.しかし、エミリーはまだ小さすぎて、計算できないので、彼女を助けてほしいです.
Input
入力ファイルの最初の行には、N,M,x,y,Kの5つの数が含まれています.NとMはダンスホールの大きさを記述し、xとyはピアノの初期位置(x行y列)である.船体の傾きについては時間の区間で記述し、1から時間を計測し、例えば「[1,3]時間で東に傾き、[4,5]時間で北に傾く」ので、ここでのKは区間の数を表す.以下のN行、各行M文字、ダンスホールの家具を説明します.i行目j列目の文字が'.',この位置が空き地であることを示す.「x」であれば、家具があることを表す.以下のK行は、si ti diとしてフォーマットされたK個の時間区間を順次記述する.時間区間[si,ti]内で船体がdi方向に傾斜していることを示す.diは1,2,3,4のうちの1つで,北,南,西,東(それぞれ対応行列中の上,下,左,右)を順に表す.入力保証区間は連続している,すなわちs 1＝1 si＝ti−1＋1(1＜i≦K)tK＝T
Output
出力ファイルは1行のみで、ピアノの滑走路の最長距離(すなわち格子数)を表す整数が含まれています.
Sample Input
4 5 4 1 3 ..xx. ..... ...x. ..... 1 3 4 4 5 1 6 7 3
Sample Output
6
タイトル:http://www.lydsy.com/JudgeOnline/problem.php?id=1499
题意:主役はマトリクスの中で上下左右に移动して、移动距离を最も长くならせて、毎回の移动の方向の最大の距离を与えて、最も长い移动距离を求めます
分析:この問題は各方向について、その方向に従ってDPをすればいいと簡単に考えることができますが、このようなDPは遅くなり、時間の複雑さはO(K*n*m*(mまたはn))です.ここでは具体的にデータを見ると、必ずタイムアウトしますが、毎回の答えはその前面の格子に関係しています.私たちはその最大値を探しています.そして、距離に関する値を加えています.単調なキューでメンテナンスできます
PS:この问题は比较的におもしろくて、その上私の华丽な1 Y、ははは
コード:
Time Limit: 3 Sec
Memory Limit: 64 MB
Submit: 490
Solved: 250
[ Submit][ Status][ Discuss]
Description
ワルツを飛び越えたの?音楽が鳴ると、メロディーに合わせて滑って踊ると、仙境を歩く快適さがありますか?よく知られているように、ワルツを踊るとき、最も重要なのは良い音楽があることです.しかし、世界で最も偉大なピアニストが一生海に漂泊していることを知っている人は少ない.彼の名前はダニー・ブドマン・T.D.レモン・1900で、友达は1900と呼んでいる.1900年、20世紀の初年に欧米を往復するクルーズ船バージニア号に生まれたが、不幸にも生まれたばかりで捨てられ、孤児になった.1900年の孤独な成長はバージニア号で、この揺れる世界を離れたことがない.彼の運命の補償かもしれないが、神はかわいい天使エミリーを世話してくれた.天使の点化かもしれませんが、1900は不思議なピアノの才能を持っています.誰も教えていません.楽譜を見たことがありませんが、彼は自分の感覚で最も人の心に沁みるメロディーを弾くことができます.1900年の音楽がクルーズ船のすべての人に歓迎された時、彼はまだ8歳で、この時の彼はすでにクルーズ船に乗って欧米大陸を50回以上往復した.ピアノの奇才とはいえ、1900年はまだ子供で、彼は普通の男の子と同じ好奇心といたずらを持っていて、ただもっとロマンチックな色にすぎない.これは風雨が入り交じった夜で、海風が波を巻いてバージニア号をたたき、クルーズ船は波とともに激しく揺れている.船の新しいサックスのマックス・トニーは船酔いし、1900年にトニーにダンスホールのピアノに乗るように呼びかけ、ピアノを固定するブレーキを緩めた.すると、ピアノは海輪の傾斜に従って滑った.正確に言えば、私たちの主役1900、ピアノ、クルーズ船は1900のメロディーとともにワルツを踊り、「パチパチ」のリズムとともにトニーの船酔い症も奇跡的に消えた.それからトニーは回顧録で、海が揺れて私たちを回転させて急速に明かりと家具をかすめて、私たちが海と一緒に踊っていることに気づいた.本当に完璧でクレイジーなダンサーが夜、金色の床でワルツを楽しく踊っているのは快適ではないかと書いた.もしかすると、私たちは一人を忘れたかもしれません.それはエミリーです.彼女は暇ではありません.彼女は適当な時に魔法をかけて1900を助けなければなりません.ピアノがダンスホールの家具にぶつからないようにしなければなりません.ダンスホールはN行M列の行列であり、行列の中のいくつかの四角い格子に家具が積み上げられており、他は空き地であると考えてもいい.ピアノは空き地で滑ることができますが、家具にぶつかったり、ダンスホールを滑ったりしてはいけません.そうしないと、ピアノや家具を壊して、付きまとう船長を引き起こします.各時刻、ピアノは船体の傾斜方向に従って隣接する四角い格子にスライドし、隣接する四角い格子は東、西、南または北にスライドすることができる.エミリーは魔法をかけるか、魔法をかけないかを選ぶことができます.魔法をかけなければ、ピアノは滑ります.魔法をかけるとピアノは動かない.エミリーは天使で、彼女は時間ごとに船体の傾斜状況を知っています.彼女はピアノをダンスホールでできるだけ長く滑らせたいと思っています.1900年はとても喜んで、トニーの船酔いの治療にも役立ちます.しかし、エミリーはまだ小さすぎて、計算できないので、彼女を助けてほしいです.
Input
入力ファイルの最初の行には、N,M,x,y,Kの5つの数が含まれています.NとMはダンスホールの大きさを記述し、xとyはピアノの初期位置(x行y列)である.船体の傾きについては時間の区間で記述し、1から時間を計測し、例えば「[1,3]時間で東に傾き、[4,5]時間で北に傾く」ので、ここでのKは区間の数を表す.以下のN行、各行M文字、ダンスホールの家具を説明します.i行目j列目の文字が'.',この位置が空き地であることを示す.「x」であれば、家具があることを表す.以下のK行は、si ti diとしてフォーマットされたK個の時間区間を順次記述する.時間区間[si,ti]内で船体がdi方向に傾斜していることを示す.diは1,2,3,4のうちの1つで,北,南,西,東(それぞれ対応行列中の上,下,左,右)を順に表す.入力保証区間は連続している,すなわちs 1＝1 si＝ti−1＋1(1＜i≦K)tK＝T
Output
出力ファイルは1行のみで、ピアノの滑走路の最長距離(すなわち格子数)を表す整数が含まれています.
Sample Input
4 5 4 1 3 ..xx. ..... ...x. ..... 1 3 4 4 5 1 6 7 3
Sample Output
6
タイトル:http://www.lydsy.com/JudgeOnline/problem.php?id=1499
题意:主役はマトリクスの中で上下左右に移动して、移动距离を最も长くならせて、毎回の移动の方向の最大の距离を与えて、最も长い移动距离を求めます
分析:この問題は各方向について、その方向に従ってDPをすればいいと簡単に考えることができますが、このようなDPは遅くなり、時間の複雑さはO(K*n*m*(mまたはn))です.ここでは具体的にデータを見ると、必ずタイムアウトしますが、毎回の答えはその前面の格子に関係しています.私たちはその最大値を探しています.そして、距離に関する値を加えています.単調なキューでメンテナンスできます
PS:この问题は比较的におもしろくて、その上私の华丽な1 Y、ははは
コード:
#include<cstdio>
#include<iostream>
using namespace std;
const int mm=222;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int f[2][mm][mm],q[mm],v[mm];
char map[mm][mm];
int g1,g2;
void solve(int x,int y,int w,int L,int c)
{
int i,l=0,r=-1,tmp;
for(i=1;i<=w;++i)
{
if(map[x][y-1]=='.')
{
tmp=f[g1][x][y]+w-i;
while(l<=r&&tmp>v[r])--r;
v[++r]=tmp;
q[r]=i;
while(i-q[l]>L)++l;
f[g2][x][y]=v[l]-w+i;
}
else l=r+1,f[g2][x][y]=-2e9;
x=x+dx[c];
y=y+dy[c];
}
}
int main()
{
int i,j,n,m,k,x,y,a,b,c,ans;
while(~scanf("%d%d%d%d%d",&n,&m,&x,&y,&k))
{
for(i=1;i<=n;++i)
scanf("%s",map[i]);
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)f[0][i][j]=-2e9;
f[0][x][y]=0;
g1=1,g2=0;
while(k--)
{
g1^=1,g2^=1;
scanf("%d%d%d",&a,&b,&c);
if(c==1)for(j=1;j<=m;++j)solve(n,j,n,b-a+1,c-1);
if(c==2)for(j=1;j<=m;++j)solve(1,j,n,b-a+1,c-1);
if(c==3)for(i=1;i<=n;++i)solve(i,m,m,b-a+1,c-1);
if(c==4)for(i=1;i<=n;++i)solve(i,1,m,b-a+1,c-1);
}
ans=0;
for(i=1;i<=n;++i)
for(j=1;j<=m;++j)
ans=max(ans,f[g2][i][j]);
printf("%d
",ans);
}
return 0;
}