B3637-DP【橙】

这题我用sort的时候大意了，从1开始使用的下标但是用sort时没加1导致排序错误，排了半天错才发现。
另外，这道题我似乎用了一种与网络上搜到了做法截然不同的自己的瞎想出来的做法，我的这个做法需要n^2级别的空间复杂度，但好在这道题数据刚刚好允许我开二维数组于是便AC了。
随后开始看时间复杂度是n^2空间复杂度是n的正解，理解了，但感觉很奇怪，主要就是不知道这个思路应该怎么凭空想出来。至于nlogn的优化算法则是压根第一时间就没看明白。

Code

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <cmath>
using namespace std;

int n,a[5000+5],b[5000+5],m[1000000+5],dp[5000+5][5000+5];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(b+1,b+1+n);
	for(int i=1,p=1;i<=n;i++)
	{
		m[b[i]]=p;
		if(b[i+1]!=b[i])p++;
	}
		
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n+1;j++)
		{
			if(m[a[i]]<j)dp[i][j]=max(1+dp[i-1][m[a[i]]],dp[i-1][j]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n][n+1]<<endl;
	return 0;
}