广州网站 制作信科便宜,东莞网站建设部落,制作静态动漫网站模板,宁波工业设计最好的公司机器人军团 时间限制: 1 Sec 内存限制: 64 MB 提交: 279 解决: 139 [提交] [状态] [命题人:admin] 题目描述 邪狼#xff1a;“怎么感觉这些机器人比我还聪明#xff1f;不是说人工智能永远不能超越人类吗#xff1f;”
天顶星人#xff1a;“你们真是目光短浅#xff0c…机器人军团 时间限制: 1 Sec 内存限制: 64 MB 提交: 279 解决: 139 [提交] [状态] [命题人:admin] 题目描述 邪狼“怎么感觉这些机器人比我还聪明不是说人工智能永远不能超越人类吗”
天顶星人“你们真是目光短浅自大而愚蠢你要知道如果有意识的智慧生命在无穷无尽的岁月里居然做不到无意识的宇宙曾做过的事产生智慧生命这就好像一只无知的猴子在琴键上跳了亿万年居然跳出了一支贝多芬第九交响曲而有智慧的生物居然几千年也学不会一支简单的小夜曲那样荒谬。如果说永远都做不到那这在你们的哲学里不就是神秘论和不可知论了吗要知道世事无绝对。”
话说在天顶星人的指导下修罗王建造了一支机器人军团机器人排成一行且身高分别为b1b2…bn。修罗王准备从中选出一组满足最长不下降子序列规则的机器人组成一支精锐卫队。所谓不下降子序列Longest Increasing SubsequenceLIS定义为设有由n个不相同的整数组成的数列b[n]若有下标i1i2…iL且b[i1]b[i2]…b[iL]则称存在一个长度为L的不下降序列。
例如13791638243718441921226315。有1316384463 长度为5的不下降子序列。但经过观察实际还有79161819212263 长度为8的不下降子序列。那么是不是还有更长的不下降子序列呢?请找出最长不下降子序列的长度。
输入 第一行为n表示n(n≤100000)个数。第二行为n个数的值。
输出 一个整数即最长不下降序列的长度。
样例输入 复制样例数据 4 1 3 1 2 样例输出 2
解题思路 用dp[i]dp[i]dp[i]来代表以iii结尾的最长上升子序列的最大长度。 因此对于每一次更新dp[i]dp[i]dp[i]时仅需从开始遍历到iii如果遍历的值会小于arr[i]arr[i]arr[i]更新依次dp[i]dp[i]dp[i]即可即 dp[i]max(dp[i],dp[j]1)dp[i]max(dp[i],dp[j]1)dp[i]max(dp[i],dp[j]1)(i:1(i:1(i:1~ n,j:1n,j:1n,j:1~ i−1)i-1)i−1)
代码
//#pragma GCC optimize(3,Ofast,inline)
#include cstdio
#include iostream
#include algorithm
#include cmath
#include cstdlib
#include cstring
#include map
#include stack
#include queue
#include vector
#include bitset
#include set
#include utility
#include sstream
#include iomanip
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define rep(i,l,r) for(int il;ir;i)
#define lep(i,l,r) for(int il;ir;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queueint,vectorint ,greaterint q;
const int maxn (int)1e5 5;
const ll mod 1e97;
int arr[100100];
int dp[100100];
int main()
{#ifndef ONLINE_JUDGEfreopen(in.txt, r, stdin);#endif//freopen(out.txt, w, stdout);//ios::sync_with_stdio(0),cin.tie(0);int n;scanf(%d,n);rep(i,1,n) {scanf(%d,arr[i]);dp[i]1;}int ans0;rep(i,1,n) {for(int j1;ji;j) {if(arr[j]arr[i]) {dp[i]max(dp[i],dp[j]1);}}}rep(i,1,n) {ansmax(ans,dp[i]);}printf(%d\n,ans);return 0;
}
