bzoj1499: [NOI2005]瑰丽华尔兹&&codevs1748 单调队列优化dp
2024-08-22 18:06:15
这道题 网上题解还是很多很好的 强烈推荐黄学长 码风真的好看 神犇传送门 学习学习 算是道单调队列优化dp的裸题吧
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=,inf=0x3f3f3f3f;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,sx,sy,k,ans;
int head,tail,now;
char a[M][M];
int f[M][M][M],q[M],pos[M];
int xi[]={,-,,,},yi[]={,,,-,};
bool pd(int x,int y){return (x>=&&x<=n&&y>=&&y<=m);}
void push_ans(int now,int w){
if(w==-inf) return ;
while(head<=tail&&q[tail]<w-now) tail--;
q[++tail]=w-now;
pos[tail]=now;
}
void dp(int i,int x,int y,int d,int l){
head=; tail=;
int now=;
while(pd(x,y)){
if(a[x][y]=='x') head=,tail=;
else push_ans(now,f[i-][x][y]);
while(head<=tail&&now-pos[head]>l) head++;
if(head<=tail) f[i][x][y]=q[head]+now;
else f[i][x][y]=-inf;
ans=max(ans,f[i][x][y]);
x+=xi[d]; y+=yi[d]; now++;
}
}
int main()
{
int x,y,d,L;
n=read(); m=read(); sx=read(); sy=read(); k=read();
for(int i=;i<=n;i++) scanf("%s",a[i]+);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
f[][i][j]=-inf;
f[][sx][sy]=;
for(int i=;i<=k;i++){
x=read(); y=read(); d=read(); L=y-x+;
if(d==) for(int j=;j<=m;j++) dp(i,n,j,d,L);
if(d==) for(int j=;j<=m;j++) dp(i,,j,d,L);
if(d==) for(int j=;j<=n;j++) dp(i,j,m,d,L);
if(d==) for(int j=;j<=n;j++) dp(i,j,,d,L);
}
printf("%d\n",ans);
return ;
}
最新文章
- List集合的removeAll(Collection<;E>; col) 和clear方法的区别
- 《C专家编程》第二章——这不是Bug,而是语言特性
- Keepalived 双机热备
- spring源码分析的书到了
- POJ 2154 【POLYA】【欧拉】
- PIL库 (Pillow)
- Mysql 笔记:
- Android 图片显示
- ListView间隔设置颜色
- Implement Queue using Stacks(用栈实现队列)
- Java Memory Management
- WPF 系统关闭模式
- 【原创】大叔经验分享(29)cdh5使用已存在的metastore数据库部署hive
- [No0000159]C# 7 中的模范和实践
- 通过 SSH 转发TCP连接数据
- 提高VS2010运行速度的技巧
- window7 触屏操作相关
- OO终章--总结博客
- codeforces675D Tree Construction
- ubuntu mysql 配置(远程访问&;&;字符集设置&;&;忽略大小写)
热门文章
- 完整的vue+vuex+api-router+database请求流程
- 转MySQL详解--索引
- 接口测试工具postman(一)下载安装说明
- 自动化测试元素查找利器firepath介绍
- Toward Convolutional Blind Denoising of Real Photographs
- Git&;GitHub&;GitBook
- 第十四次ScrumMeeting会议
- HBase 高可用性
- LTE:上行调度请求(Scheduling Request,SR) LTE:下行资源分配类型
- lnmp1.4,400,500,错误