当前位置:网站首页>最长上升子序列模型 AcWing 1012. 友好城市
最长上升子序列模型 AcWing 1012. 友好城市
2022-07-07 12:08:00 【T_Y_F666】
最长上升子序列模型 AcWing 1012. 友好城市
原题链接
算法标签
DP 线性DP 最长上升子序列
思路
将友好城市一端进行排序, 另一端最长上升序列即为答案
代码
#include<bits/stdc++.h>
#define int long long
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>=b;--i)
using namespace std;
const int N = 5005, INF = 0x3f3f3f3f;
int f[N], f1[N], a[N];
inline int read(){
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void put(int x) {
if(x<0) putchar('-'),x=-x;
if(x>=10) put(x/10);
putchar(x%10^48);
}
struct Node{
int a,b;
}node[N];
bool cmp(Node A, Node B){
return A.b<B.b;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n=read(),ans=0;
rep(i, 0, n){
node[i].a=read(),node[i].b=read();
}
sort(node, node+n, cmp);
rep(i, 0, n){
f[i]=1;
rep(j, 0, i){
if(node[j].a<node[i].a){
f[i]=max(f[i], f[j]+1);
}
}
ans=max(ans, f[i]);
}
printf("%lld\n", ans);
}
y总代码
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 5010;
int n;
PII city[N];
int f[N];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d%d", &city[i].first, &city[i].second);
sort(city, city + n);
int res = 0;
for (int i = 0; i < n; i ++ )
{
f[i] = 1;
for (int j = 0; j < i; j ++ )
if (city[i].second > city[j].second)
f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
}
printf("%d\n", res);
return 0;
}
tips
双关键字排序, 使用pair, 无需新建结构体。运行时间一致
原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈
边栏推荐
- 请问,在使用flink sql sink数据到kafka的时候出现执行成功,但是kafka里面没有数
- Vmware共享主机的有线网络IP地址
- 交付效率提升52倍,运营效率提升10倍,看《金融云原生技术实践案例汇编》(附下载)
- Use day JS let time (displayed as minutes, hours, days, months, and so on)
- Excuse me, when using Flink SQL sink data to Kafka, the execution is successful, but there is no number in Kafka
- 【面试高频题】难度 2.5/5,简单结合 DFS 的 Trie 模板级运用题
- [1] ROS2基础知识-操作命令总结版
- Environment configuration
- Redis 核心数据结构 & Redis 6 新特性详
- 请问,PTS对数据库压测有好方案么?
猜你喜欢
带你掌握三层架构(建议收藏)
Realize the IP address home display function and number home query
高等數學---第八章多元函數微分學1
Vmware共享主机的有线网络IP地址
最佳实践 | 用腾讯云AI意愿核身为电话合规保驾护航
得物客服热线的演进之路
Sliding rail stepping motor commissioning (national ocean vehicle competition) (STM32 master control)
Supply chain supply and demand estimation - [time series]
Build a secure and trusted computing platform based on Kunpeng's native security
DID登陆-MetaMask
随机推荐
FC连接数据库,一定要使用自定义域名才能在外面访问吗?
MySQL error 28 and solution
Seven propagation behaviors of transactions
Did login metamask
Interface automation test - solution of data dependency between interfaces
Leecode3. Longest substring without repeated characters
Sliding rail stepping motor commissioning (national ocean vehicle competition) (STM32 master control)
Build a secure and trusted computing platform based on Kunpeng's native security
Enregistrement de la navigation et de la mise en service du robot ROS intérieur (expérience de sélection du rayon de dilatation)
【面试高频题】难度 2.5/5,简单结合 DFS 的 Trie 模板级运用题
云计算安全扩展要求关注的安全目标和实现方式区分原则有哪些?
toRaw和markRaw
PHP中用下划线开头的变量含义
Deep understanding of array related problems in C language
Supply chain supply and demand estimation - [time series]
Take you to master the three-tier architecture (recommended Collection)
Cesium 已知一点经纬度和距离求另一个点的经纬度
Laravel form builder uses
【日常训练】648. 单词替换
接口自动化测试-接口间数据依赖问题解决