机器人军团【动态规划】

78 阅读 0 评论 52 点赞

我是靠谱客的博主陶醉故事，这篇文章主要介绍机器人军团【动态规划】，现在分享给大家，希望可以做个参考。

机器人军团
时间限制: 1 Sec 内存限制: 64 MB
提交: 279 解决: 139
[提交] [状态] [命题人:admin]
题目描述
邪狼：“怎么感觉这些机器人比我还聪明？不是说人工智能永远不能超越人类吗？”

天顶星人：“你们真是目光短浅，自大而愚蠢！你要知道，如果有意识的智慧生命在无穷无尽的岁月里居然做不到无意识的宇宙曾做过的事（产生智慧生命），这就好像一只无知的猴子在琴键上跳了亿万年居然跳出了一支贝多芬第九交响曲，而有智慧的生物居然几千年也学不会一支简单的小夜曲那样荒谬。如果说永远都做不到，那这在你们的哲学里，不就是神秘论和不可知论了吗？要知道世事无绝对。”

话说在天顶星人的指导下，修罗王建造了一支机器人军团，机器人排成一行，且身高分别为b1，b2，…，bn。修罗王准备从中选出一组满足最长不下降子序列规则的机器人组成一支精锐卫队。所谓不下降子序列（Longest Increasing Subsequence，LIS）定义为：设有由n个不相同的整数组成的数列b[n]，若有下标i1<i2<…<iL且b[i1]<b[i2]<…<b[iL]，则称存在一个长度为L的不下降序列。

例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。有13<16<38<44<63 长度为5的不下降子序列。但经过观察，实际还有7<9<16<18<19<21<22<63 长度为8的不下降子序列。那么是不是还有更长的不下降子序列呢?请找出最长不下降子序列的长度。

输入
第一行为n，表示n(n≤100000)个数。第二行为n个数的值。

输出
一个整数，即最长不下降序列的长度。

样例输入
复制样例数据
4
1 3 1 2
样例输出
2

解题思路：
用 $d p [i]$ 来代表以 $i$ 结尾的最长上升子序列的最大长度。
因此，对于每一次更新 $d p [i]$ 时，仅需从开始遍历到 $i$ ，如果遍历的值会小于 $a r r [i]$ ，更新依次 $d p [i]$ 即可，即
$d p [i] = m a x (d p [i], d p [j] + 1)$ $(i : 1$ ~ $n, j : 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 i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int arr[100100];
int dp[100100];
int main() 
{
    #ifndef ONLINE_JUDGE
    freopen("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 ans=0;
    rep(i,1,n) {
    	for(int j=1;j<i;j++) {
    		if(arr[j]<arr[i]) {
    			dp[i]=max(dp[i],dp[j]+1);
    		}
    	}
    }
    rep(i,1,n) {
   		ans=max(ans,dp[i]);
   	}
   	printf("%dn",ans);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//#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 i=l;i<=r;i++)
#define lep(i,l,r) for(int i=l;i>=r;i--)
#define ms(arr) memset(arr,0,sizeof(arr))
//priority_queue<int,vector<int> ,greater<int> >q;
const int maxn = (int)1e5 + 5;
const ll mod = 1e9+7;
int arr[100100];
int dp[100100];
int main() 
{
    #ifndef ONLINE_JUDGE
    freopen("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 ans=0;
    rep(i,1,n) {
    	for(int j=1;j<i;j++) {
    		if(arr[j]<arr[i]) {
    			dp[i]=max(dp[i],dp[j]+1);
    		}
    	}
    }
    rep(i,1,n) {
   		ans=max(ans,dp[i]);
   	}
   	printf("%dn",ans);
    return 0;
}