社区讨论
蒟蒻刷DP题80分求助
P1434[SHOI2002] 滑雪参与者 3已保存回复 10
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 10 条
- 当前快照
- 1 份
- 快照标识符
- @lod12d0i
- 此快照首次捕获于
- 2023/10/30 23:01 2 年前
- 此快照最后确认于
- 2023/11/05 09:18 2 年前
总体思路:
将节点从高到低排序依次扩展,可以保证是最优解
WARNING:极差码风注意
CPP#include <iostream>
#include <cstdio>
#include <algorithm>
using std::sort;
struct Node
{
int x, y, h;
}s[10900];
struct OriginalGraph
{
int h, w;
}g[109][109];
int r, c, ans;
int v(int pos1, int pos2)
{
return ((pos1-1)*r+pos2);
}
int comp(const Node s1, const Node s2)
{
return s1.h>s2.h;
}
int main()
{
scanf("%d%d", &r, &c);
for(register int i=1; i<=r; ++i)
{
for(register int j=1; j<=c; ++j)
{
scanf("%d",&g[i][j].h);
s[v(i,j)].h=g[i][j].h;
s[v(i,j)].x=i;
s[v(i,j)].y=j;
g[i][j].w=1;
}
}
sort(s+1, s+r*c+1, comp);
for(register int i=1; i<=r*c; ++i)
{
if(g[s[i].x-1][s[i].y].h>g[s[i].x][s[i].y].h&&g[s[i].x-1][s[i].y].w+1>g[s[i].x][s[i].y].w&&s[i].x-1>0)
{
g[s[i].x][s[i].y].w=g[s[i].x-1][s[i].y].w+1;
}
if(g[s[i].x][s[i].y-1].h>g[s[i].x][s[i].y].h&&g[s[i].x][s[i].y-1].w+1>g[s[i].x][s[i].y].w&&s[i].y-1>0)
{
g[s[i].x][s[i].y].w=g[s[i].x][s[i].y-1].w+1;
}
if(g[s[i].x+1][s[i].y].h>g[s[i].x][s[i].y].h&&g[s[i].x+1][s[i].y].w+1>g[s[i].x][s[i].y].w&&s[i].x+1<=r)
{
g[s[i].x][s[i].y].w=g[s[i].x+1][s[i].y].w+1;
}
if(g[s[i].x][s[i].y+1].h>g[s[i].x][s[i].y].h&&g[s[i].x][s[i].y+1].w+1>g[s[i].x][s[i].y].w&&s[i].y+1<=c)
{
g[s[i].x][s[i].y].w=g[s[i].x][s[i].y+1].w+1;
}
if(g[s[i].x][s[i].y].w>ans)
{
ans=g[s[i].x][s[i].y].w;
}
}
printf("%d",ans);
return 0;
}
1和2点就是过不去……
被黄题难住果然还是不应该……
请指教我!(他力本愿)
回复
共 10 条回复,欢迎继续交流。
正在加载回复...