题目
https://cn.vjudge.net/problem/Kattis-heightpreservation
题意
给你个图，为你改变高度后但不改变相对高低 问有的最小高度为多少
思路
思维 排序后一个点一个点贪心
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i = (a);i <= (b);i++)
using namespace std;
typedef long long ll;
struct node
{ll x,y,w;}a[1000005];
ll l[1000006],r[1000006],l1[1000006],r1[1000006];
bool cmp(node a,node b)
{return a.w < b.w;
}
int main()
{ll n,m;scanf("%lld%lld",&n,&m);ll p= 0;for(ll i = 1;i <= n;i++){for(ll j = 1;j <= m;j++){ll x;scanf("%lld",&x);a[++p].x = i,a[p].y = j,a[p].w = x;}}sort(a+1,a+1+p,cmp);memset(l1,0,sizeof(l1));memset(r1,0,sizeof(r1));memset(l,0,sizeof(l));memset(r,0,sizeof(r));ll ans = 1;rep(i,1,n*m){ll x = a[i].x,y = a[i].y,w = a[i].w;ll qw = max(l[x] + (l1[x]==w?0:1),r[y]+(r1[y]==w?0:1));l[x] = r[y] = qw;l1[x] = r1[y] = w;ans = max(ans,qw);}printf("%lld\n",ans);return 0;
}建边 跑最长路
#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#define rep(i,a,b) for(ll i = (a);i <= (b);i++)
using namespace std;
typedef long long ll;
struct node
{ll x,w;node(ll xx,ll ww){x = xx,w = ww;}bool operator <(const node &b) const{if(w == b.w) return x < b.x;return w < b.w;}
};
struct nodee
{ll v,w;nodee(ll vv,ll ww){v = vv;w = ww;}
};
vector<node> l[1000006],r[1000006];
vector<nodee> edge[1000006];
ll deep[1000006];
ll n,m;
ll id(ll x,ll y)
{return x*m+y;
}
ll dfs(ll u)
{if(deep[u] != 0) return deep[u];deep[u] = 1;for(ll i =0;i < edge[u].size();i++){ll v = edge[u][i].v;deep[u] = max(deep[u],dfs(v)+edge[u][i].w);}return deep[u];
}
int main()
{if(scanf("%lld%lld",&n,&m)){}rep(i,0,n-1){rep(j,0,m-1){ll x;if(scanf("%lld",&x)){}l[i].push_back(node(id(i,j),x));r[j].push_back(node(id(i,j),x));}}rep(i,0,n-1){sort(l[i].begin(),l[i].end());rep(j,1,m-1){ll u = l[i][j-1].x,v = l[i][j].x;if(l[i][j-1].w == l[i][j].w)edge[u].push_back(nodee(v,0));else edge[u].push_back(nodee(v,1));}}rep(j,0,m-1){sort(r[j].begin(),r[j].end());rep(i,1,n-1){ll u = r[j][i-1].x,v = r[j][i].x;if(r[j][i-1].w == r[j][i].w)edge[u].push_back(nodee(v,0));elseedge[u].push_back(nodee(v,1));}}ll ans = 0;memset(deep,0,sizeof(deep));rep(i,0,n*m-1){if(deep[i] == 0) dfs(i);ans = max(ans,deep[i]);}printf("%lld\n",ans);return 0;
}