dp--최장 상승 하위 시퀀스

1759:최장 상승자 서열

총 시간 제한:
2000ms
 
메모리 제한:
65536kB
묘사
한 수의 서열
저당
b1 b2 < ... bS에서 우리는 이 서열이 상승했다고 말했다.주어진 시퀀스에 대해(
a1, 
a2, ..., 
aN), 우리는 상승하는 하위 서열을 얻을 수 있다(
ai1, 
ai2, ..., 
aiK), 여기 1 <=
i1 i2 < ... iK <= N.예를 들어 서열(1,7,3,5,9,4,8)에 대해 그것의 일부 상승자 서열이 있다. 예를 들어 (1,7),(3,4,8) 등이다.이 서열들 중 가장 긴 길이는 4이다. 예를 들어 서열(1,3,5,8)이다.
당신의 임무는 주어진 서열에 대해 가장 긴 상승자 서열의 길이를 구하는 것입니다.
입력
입력한 첫 번째 행은 시퀀스의 길이 N(1 <= N <= 1000)입니다.두 번째 행에서는 0~10000의 범위에 해당하는 시퀀스의 N개의 정수를 제공합니다.
출력
최장 상승 서열의 길이.
dp[i]는 i를 끝으로 형성된 최장 상승 서열을 나타낸다
매번 [i]>a[j]일 때, 즉 j는 a의 뒤에 놓을 수 있다는 것을 설명한다.
dp[i] = max(dp[j]+1,dp[i])

1     for (int i = 1;i <= n;i++)
2         for (int j = 1;j <= i-1;j++)
3         {
4             if (a[j]<a[i]) 
5             dp[i] = max(dp[j]+1,dp[i]);
6         }

 
전체 코드:

 1 #include 
 2 #include 
 3 using namespace std;
 4 int dp[1010];
 5 int main()
 6 {
 7     int n;
 8     int a[1010];
 9     scanf ("%d",&n);
10     int dp[1010];
11     for (int i = 1;i <= n;i++)
12     {
13         scanf ("%d",&a[i]);
14         dp[i] = 1;
15     }
16     for (int i = 1;i <= n;i++)
17         for (int j = 1;j <= i-1;j++)
18         {
19             if (a[j]<a[i]) 
20             dp[i] = max(dp[j]+1,dp[i]);
21         }
22     int ans=0;
23     for (int i =1 ;i <= n;i++)
24         ans=max(dp[i],ans);
25     cout<<ans;
26     return 0;
27 }