codeforces 255C DP yy

100 阅读 0 评论 66 点赞

我是靠谱客的博主天真小鸭子，最近开发中收集的这篇文章主要介绍codeforces 255C DP yy，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一开始以为是求最长字串的变种，自作聪明，用map处理，到了后期果断TLE

唉，无耐，只能参考大神代码，发现自己真是弱到家....

做法：先对最终形成的数列有个直观的想象，是锯齿形的是吧。现在要找的就是这些锯齿中最长的一个，就以每个锯齿为划分状态,然后为了使生成的矩阵尽可能长，就从头到它自己之前找底座（和他相等的一个元素），一开始基座为0.只要想和当前数结合，那么生成的锯齿肯定经过这个基座，所有可以不用怕漏考虑。

/***
锯齿图要注意了
贪心，找底座。
****/
#include<cstdio>
#include<algorithm>
#define LMT 4005
using namespace std;
int dp[LMT][LMT],a[LMT];
int main(void)
{
int n,last,j,ans=-1;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
for( j=last=0;j<i;j++)
{
dp[i][j]=dp[j][last]+1;
if(a[i]==a[j])last=j;
ans=max(ans,dp[i][j]);
}
}
printf("%dn",ans);
}