题目描述
有一个H*W的网格,某些网格中有数字a[i],其余为0
(a,b)可以移动到(c,d)必须满足两个条件
1.(a,b)网格中的数字严格小于(c,d)
2.(a,b)与(c,d)在同一列或者一行
求每个数字能够走到的格子数量
输入样例
3 3 7
1 1 4
1 2 7
2 1 3
2 3 5
3 1 2
3 2 5
3 3 5
输出样例
1
0
2
0
3
1
0
算法
(dp)
从题目给出的数据范围可以看出,我们想开一个H*W的数组是不太肯能的,所以在这里我们换一个思路
用dp[i]表示数字i能走到的最大数量是多少
我们不如从大到小枚举出现的数字,之后来更新每一列能够走到的最大值,每一行能走到的最大值以此来算出dp[i]
思路:
1.从大到小枚举出现的数字
2.dp[i]=max(数字i所在列的最大值,数字i所在的行的最大值)
3.更新数字i所在列的最大值,数字i所在的行的最大值
1.存取数据
由于要用到数字,数字在的行,数字在的列
所以在这里我用map<int,vector<int> >mp 来存储数据为a[i]的时候的i
r[]存储i所在的行
c[]存储i所在的列
rm[]:存储i行中的最大值
cm[]:存储j列中的最大值
2.状态转移方程
for(auto t=mp.rbegin();t!=mp.rend();t++)//用反向迭代器从大到小枚举出现的数字
{
for(auto i:t->y)
{
f[i]=max(rm[r[i]],cm[c[i]]);//dp[i]=max(数字i所在列的最大值,数字i所在的行的最大值)
}
for(auto i:t->y)//更新数字i所在列的最大值,数字i所在的行的最大值
{
rm[r[i]]=max(rm[r[i]],f[i]+1);
cm[c[i]]=max(cm[c[i]],f[i]+1);
}
}
C++代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<unordered_map>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N=2e5+10;
int f[N],r[N],c[N];
int rm[N],cm[N];
int a[N];
map<int,vector<int> >mp;
#define x first
#define y second
int main()
{
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=k;i++)
{
scanf("%d %d %d",&r[i],&c[i],&a[i]);
mp[a[i]].push_back(i);
}
for(auto t=mp.rbegin();t!=mp.rend();t++)
{
for(auto i:t->y)
{
f[i]=max(rm[r[i]],cm[c[i]]);
}
for(auto i:t->y)
{
rm[r[i]]=max(rm[r[i]],f[i]+1);
cm[c[i]]=max(cm[c[i]],f[i]+1);
}
}
for(int i=1;i<=k;i++) cout<<f[i]<<"\n";
}