Codeforces Round #156 (Div. 1)A dp
发布时间：2020-12-13 20:41:47 所属栏目：PHP教程 来源：网络整理
导读：//对每一个数进行1个编号， //dp[i][j]表示第i个数其前面是第j个数得到的最长子序列 //dp[i][j] = dp[i][j] = dp[last[j]][map[num[i]]] 1; //last[j]是编号为j的数的最后出现的位置 //map[num[i]]第i个数的编号 #includeiostream #includecstdio #includecst
|
//对每一个数进行1个编号， //dp[i][j]表示第i个数其前面是第j个数得到的最长子序列 //dp[i][j] = dp[i][j] = dp[last[j]][map[num[i]]] + 1; //last[j]是编号为j的数的最后出现的位置 //map[num[i]]第i个数的编号 #include<iostream> #include<cstdio> #include<cstring> using namespace std ; const int maxn = 4010 ; const int maxm = 1000010; int map[maxm]; int last[maxn]; int dp[maxn][maxn] ; int num[maxn] ; int main() { int n; while(~scanf("%d",&n)) { for(int i = 1;i <= n;i++) scanf("%d",&num[i]) ; int len = 1; memset(map,sizeof(map)); for(int i = 1;i <= n;i++) if(!map[num[i]]) map[num[i]] = len++ ; memset(dp,sizeof(dp)) ; int ans = 1; last[map[num[1]]] = 1; for(int i = 1;i <= len;i++) dp[1][i] = 1; for(int i = 2;i <= n;i++) { for(int j = 1;j < len;j++) { dp[i][j] = dp[last[j]][map[num[i]]] + 1; ans = max(dp[i][j],ans) ; } last[map[num[i]]] = i; } printf("%d ",ans) ; } } （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |