解题报告:hdu1257 LIS裸题
2024-08-30 21:25:31
2017-09-02 17:28:44
writer:pprp
那个裸题练练手,讲解在之前的博客中提到了
代码如下:
/*
@theme:hdu1257
@writer:pprp
@begin:17:13
@end:17:26
@declare:LIS的裸题,温习一下
@error:注意题目中说明了是多组数据
@date:2017/9/2
*/ #include <bits/stdc++.h> using namespace std;
const int maxn = ;
int arr[maxn];
int dp[maxn]; int main()
{
//freopen("in.txt","r",stdin);
int N,Max = ;
while(cin >> N)
{
Max = ;
for(int i = ; i < N; i++)
{
dp[i] = ;
cin >> arr[i];
for(int j = ; j < i ; j++)
{
if(arr[j] < arr[i])
{
dp[i] = max(dp[j]+,dp[i]);
}
}
Max = max(Max,dp[i]);
}
cout << Max << endl;
} return ;
}
第二种不用dp的解法:
代码如下:
/*
@theme:hdu1257
@writer:pprp
@begin:17:13
@end:17:36
@declare:LIS的裸题,温习一下
@error:
@date:2017/9/2
*/ #include <bits/stdc++.h> using namespace std;
const int maxn = ;
int arr[maxn];
int tmp[maxn]; int main()
{
//freopen("in.txt","r",stdin);
int N,len = ;
while(cin >> N)
{
len = ;
cin >> arr[];
tmp[len] = arr[];
for(int i = ; i < N ; i++)
{
cin >> arr[i];
if(arr[i] > tmp[len])
{
len++;
tmp[len] = arr[i];
}
else
*lower_bound(tmp,tmp+len,arr[i]) = arr[i];
}
cout << len << endl;
} return ;
}
最新文章
- TWS笔试题---回家想了想答案,希望对jobseeker有帮助
- ReactiveCocoa 5.0 初窥:可能是最痛的一次升级
- Simple Molecules(简单)
- 浅谈Exchange 2013开发-如何操作邮件的附件
- json+一般处理程序读取数据库数据
- BAT带队烧钱圈地华为们猛追云计算
- android 签名被篡改(Keystore was tampered with, or password was incorrect)
- 什么是 CGI,什么是 IIS,什么是VPS
- java泛型操作复习,以及讲解在android中使用的场景
- asp.net 第三方UI控件 Telerik KendoUI 之 TreeVIew 的用法记录
- windows 安装Mysql压缩包
- AndroidDevTools
- Tiny4412中断介绍
- 吴恩达机器学习笔记26-样本和直观理解1(Examples and Intuitions I)
- Codeforces.741D.Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths(dsu on tree 思路)
- centos6.5安装mongodb2.6
- Echarts饼图显示模板
- Java实时监控类库Metrics
- 【BZOJ1032】[JSOI2007]祖玛(动态规划)
- [RxJS] Build your own RxJS