2021牛客寒假算法基础集训营3 I.序列的美观度

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了2021牛客寒假算法基础集训营3 I.序列的美观度，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含913字，纯文字阅读大概需要2分钟。

内容图文

题目链接

思路

这道题可以用DP来解决，我们首先需要考虑的是转移状态。若我们用DP[i]表示从1到i之间的最大序列美观度，则可以推导出若当前整数与前一个不同，则直接继承前一个的DP，或者也可以从上一个与当前数相同的位置转移而来，只要将其美观度加一即可。于是我们可以在输入时预处理好各个数字在序列中所对应的前一个相同位置并用数组sit进行记录即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int maxn=1e7+5;
typedef long long ll;
const ll inf=1e14;
ll ans,a[maxn],dp[maxn],sit[maxn],last[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sit[i]=last[a[i]];//sit用来记录上一个与当前数相同的数出现的位置
        last[a[i]]=i;//last用来记录某个数上一次出现的位置
    }
    for(int i=2;i<=n;i++)
    {
        if(!sit[i])
            dp[i]=max(dp[i-1],dp[sit[i]]);//当前数还未出现过的状态下，无法从前一个状态+1转移
        else
            dp[i]=max(dp[i-1],dp[sit[i]]+1);
    }
    cout<<dp[n]<<endl;
    return 0;
}

内容总结

以上是互联网集市为您收集整理的2021牛客寒假算法基础集训营3 I.序列的美观度全部内容，希望文章能够帮你解决2021牛客寒假算法基础集训营3 I.序列的美观度所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---