ZCMU - 1961: 引水入城
发布日期:2021-06-30 23:40:51
浏览次数:2
分类:技术文章
本文共 1599 字,大约阅读时间需要 5 分钟。
题目链接:
题目大意:略。
解题思路:通过第一行对应的最后一行的各个区间范围(dfs)来进行(dp)操作。
AC 代码
#include#include #define mem(a,b) memset(a,b,sizeof a);#define INF 0x3f3f3f3fusing namespace std;typedef long long ll;const int maxn=510;const int dir[4][2]={-1,0,1,0,0,-1,0,1};struct node{ int l,r; }seg[maxn][maxn];int n,m,fail;int g[maxn][maxn], vis[maxn][maxn], dp[maxn];void init(){ fail=0; mem(vis,0); mem(dp,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(i!=n) seg[i][j].l=maxn,seg[i][j].r=0; else seg[i][j].l=seg[i][j].r=j;}void dfs(int x,int y){ if(vis[x][y]) return; vis[x][y]=1; for(int i=0;i<4;i++) { int dx=x+dir[i][0], dy=y+dir[i][1]; if(dx<1||dy<1||dx>n||dy>m||g[dx][dy]>=g[x][y]) continue; dfs(dx,dy); seg[x][y].l=min(seg[x][y].l,seg[dx][dy].l); seg[x][y].r=max(seg[x][y].r,seg[dx][dy].r); }}int main(){ while(~scanf("%d%d",&n,&m)) { init(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&g[i][j]); for(int j=1;j<=m;j++) dfs(1,j); for(int j=1;j<=m;j++) fail+=!vis[n][j]; if(fail){ printf("0\n%d\n",fail); continue; } for(int j=1;j<=m;j++) { for(int k=seg[1][j].l; k<=seg[1][j].r; k++) { // dp[k]>dp[seg[1][j].l-1] 此题这条件不加也对,看样例,因为如果第1行6这个水站可以假设可以通过8下面对应的, // 那么必须要加这条加以更新,但是此题的特殊性导致6水站受限制于前一个水站的 l(字母) if(!dp[k] || dp[k]>dp[seg[1][j].l-1]) dp[k]=1+dp[seg[1][j].l-1]; } } printf("1\n%d\n",dp[m]); } return 0;}
转载地址:https://lux-sun.blog.csdn.net/article/details/81148040 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
关注你微信了!
[***.104.42.241]2024年04月21日 23时42分16秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
leetcode46 全排列
2019-04-30
leetcode 122 买卖股票的最佳时机II
2019-04-30
leetcode 309 最佳买卖股票含冷冻期
2019-04-30
leetcode 714 买卖股票的最佳时机含手续费
2019-04-30
leetcode3 无重复字符的最长子串
2019-04-30
leetcode 1143. 最长公共子序列
2019-04-30
leetcode 83. 删除排序链表中的重复元素
2019-04-30
智能体 Intelligent Agent
2019-04-30
Python 之 histogram直方图
2019-04-30
Python 之 Scatter散点图
2019-04-30
Python实现决策树 Desision Tree & 可视化
2019-04-30
决策树 Decision tree
2019-04-30
nominal和ordinal & 数据处理中四种基本数据类型
2019-04-30
Grid SearchCV(网格搜索)& Python实现
2019-04-30
单目深度估计 monodepth2模型 代码
2019-04-30
位图索引Bitmap indexes
2019-04-30