HDU 5009（dp + 双向链表的巧妙运用）

素颜马尾好姑娘i 2022-05-14 11:51 141阅读 0赞

[http://acm.hdu.edu.cn/showproblem.php?pid=5009][http_acm.hdu.edu.cn_showproblem.php_pid_5009]

这个题转移好想，时间优化不好想， 看了别人的思路，用双向链表优化，自己想到去链表里查找已经出现的元素也会花很多时间，一直没想出来，看了代码才知道，可以用map存一下前一个的位置，当有重复出现的时候， 只要将那个元素的删掉即可，也就是把他的前驱和后继相连，也就是为什么用双向链表了。

因为如果一个一个涂也就是花费为n，所以往前找的时候不要超过sqrt（n）种颜色。

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=5e4+10;
    int dp[N], c[N], pre[N], nxt[N];
    map<int, int> vis;
    
    int main(){
        int n;
    
        while(~scanf("%d", &n)){
            vis.clear();
            c[0]=-1; pre[0]=-1; nxt[0]=1;
    
            for(int i=1; i<=n; i++){
                scanf("%d", &c[i]);
                pre[i]=i-1; nxt[i]=i+1;
            }
    
            memset(dp, 0x3f, sizeof dp);
            dp[0]=0;
            for(int i=1; i<=n; i++){
    
                if(vis[c[i]]){
                    int pos=vis[c[i]];
    
                    nxt[pre[pos]]=nxt[pos];
                    pre[nxt[pos]]=pre[pos];
                    vis[c[i]]=i;
                }
                else vis[c[i]]=i;
    
                for(int j=pre[i], cnt=1; j>=0 && cnt*cnt<=i; j=pre[j], cnt++){
                    dp[i]=min(dp[i], dp[j]+cnt*cnt);
                }
            }
    
            printf("%d\n", dp[n]);
    
        }
    
    
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5009]: http://acm.hdu.edu.cn/showproblem.php?pid=5009

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关双向链表

一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个链接：一个指向前一个节点，当此节点为第一个节点时，指向空值；而另一个指向下一个节点，当此节点为最后一个节点时，指向空

灰太狼/ 2022年12月21日 04:54/ 0 赞/ 195 阅读

相关双向链表

一：双向链表双向链表的节点包含数据域，前置指针域和后置指针域 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_

ゝ一世哀愁。/ 2022年11月05日 12:57/ 0 赞/ 195 阅读

相关双向链表

前面叙述了关于单链表、双端链表、有序链表的结点插入以及遍历查找等示例。这几种链表都只能从前往后进行遍历，反向遍历是非常麻烦的一件事。考虑一下下面这个情况：如果文本编辑

亦凉/ 2022年07月18日 05:29/ 0 赞/ 215 阅读

相关双向链表

一、解析在单链表中，有了next指针，要查找下一节点的时间复杂度为O(1)，如果要查找的是上一节点的话，最坏的时间复杂度是O(n)了，以为每次都要从头开始查找。为了克服这个

「爱情、让人受尽委屈。」/ 2022年07月03日 13:57/ 0 赞/ 274 阅读

相关双向链表

/双向链表/ include<stdio.h> typedef struct dbnode { int num;

骑猪看日落/ 2022年06月16日 13:08/ 0 赞/ 209 阅读

相关双向链表和双向循环链表

双向链表和双向循环链表和单向链表相比，多了一个前驱结点。如果他为空，那么next和prior都指向自己。而对于双循环链表，只需要最后一个元素的next指向head->n

╰+哭是因爲堅強的太久メ/ 2022年05月16日 01:29/ 0 赞/ 276 阅读

相关 HDU 5009（dp + 双向链表的巧妙运用）

[http://acm.hdu.edu.cn/showproblem.php?pid=5009][http_acm.hdu.edu.cn_showproblem.php_pid

素颜马尾好姑娘i/ 2022年05月14日 11:51/ 0 赞/ 142 阅读

相关双向链表

Problem Description 学会了单向链表，我们又多了一种解决问题的能力，单链表利用一个指针就能在内存中找到下一个位置，这是一个不会轻易断裂的链。但单链表有一个弱

忘是亡心i/ 2022年05月10日 04:34/ 0 赞/ 282 阅读

相关双向链表

题目描述构建一个双向链表并进行删除和插入操作，按要求输出。输入输入：第一行输入元素个数M 第二行输入M个元素第三行输入删除位置第四行输入插入位

野性酷女/ 2022年04月04日 05:48/ 0 赞/ 262 阅读

相关双向链表

【一】双向链表 > 单向链表，查找的只能是一个方向，而双向链表可以向前或向后查找。 > 单向链表不能自我删除，需要靠辅助节点；而双向链表可以自我删除 > 双向链表中的

小咪咪/ 2021年08月12日 00:11/ 0 赞/ 434 阅读