Fork me on GitHub

动态规划算法

动态规划(dp)介绍。

知乎dalao的讲解,讲的很清晰了。
什么是动态规划?动态规划的意义是什么?

什么是动态规划?动态规划的意义是什么?

2篇帖子介绍的很好。(mua)

大家仔细看看应该很容易弄懂的。(逃。

直接从我们这周的DP题目开始搞事吧(hiahia~~)PS:这周题目真的是很好翻译。。。没有什么高级词汇。

题目

A - Longest Ordered Subsequence

A numeric sequence of ai is ordered if a1 < a2 < … < aN. Let the subsequence of the given numeric sequence ( a1, a2, …, aN) be any sequence ( ai1, ai2, …, aiK), where 1 <= i1 < i2 < … < iK <= N. For example, sequence (1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e. g., (1, 7), (3, 4, 8) and many others. All longest ordered subsequences are of length 4, e. g., (1, 3, 5, 8).

Your program, when given the numeric sequence, must find the length of its longest ordered subsequence.
Input
The first line of input file contains the length of sequence N. The second line contains the elements of sequence - N integers in the range from 0 to 10000 each, separated by spaces. 1 <= N <= 1000
Output
Output file must contain a single integer - the length of the longest ordered subsequence of the given sequence.

Sample Input

1
2
7
1 7 3 5 9 4 8

Sample Output

1
4

题目意思很裸,we should find the length of the longest ordered subequence of the given sequence。结合样例给的英文,翻译出来的意思就是叫我去找最长的递增子序列的长度。emmm。

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
#include<iostream>
#include<cstring>
#define max(a,b) a>b?a:b
using namespace std;
int a[1050],dp[1050];
int c=0;
int main()
{
int n;
while(cin>>n)
{
memset(dp,0,sizeof(dp));//每次循环记得清零。
memset(a,0,sizeof(a));
for(int i=1;i<=n;i++)
{
cin>>a[i];
dp[i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
//根据题目要求就是有序子数列中前一个数字要比后一个小。
if(a[i]>a[j])//如果后面 这个数能够
{
dp[i]=max(dp[i],dp[j]+1);
}
}
}
for(int i=1;i<=n;i++)
{
c=max(c,dp[i]);
}
cout<<c<<endl;
}
return 0;
}
-------------本文结束感谢您的阅读-------------