传送门

题目大意:给n个珠子涂成目标颜色。每次可以涂相邻的一些珠子,花费是这些珠子中颜色种数k的平方。求最小花费。

思路:双向链表优化dp。dp[i]表示涂完前i个所花的最小代价,显然有dp[i]=min{dp[j]+num(j+1,i)^2},其中1<=j<i,num(j+1,i)表示区间[j+1,i]的颜色个数。

这样复杂度为O(n^2)显然超时。那么需要优化一下,比如第二组测试数据3 4 2 4 4 2 4 3 2 2,假设dp[1]…dp[8]已更新完毕,现在要更新dp[9],可以看到a[9]为2,按照原始的dp[i]=min{dp[j]+num(j+1,i)^2},
i=9,枚举j=8,dp[9]=min{dp[9],dp[8]+1^2};j=7,dp[9]=min{dp[9],dp[7]+2^2};现在貌似没什么变化。。。
j=6,这里就神奇了,如果dp[9]=min{dp[9],dp[6]+3^2},那么这个就太弱了,因为此时2 4 3是连着涂的,但是2之前是3 4 2 4 4,这些如果跟着一起涂,那么仍然是3^2的代价,但前面的数字变少了,显然这种更优。
于是乎dp[9]=min{dp[9],dp[0]+3^2},可以看到6直接跳到了0,为什么这么跳?因为这之前都是些234啊,重复了没必要保存。所以在dp时,我们只需要维护好前后关系即可。
比如当前dp第i位,那么即a[i]加进来,所以之前如果有a[i]值的必须删掉,具体双向链表维护。因此可以看到任意时刻,每种颜色只会保存一次,复杂度就降下来了。
但仍然可以给出坑爹的数据,比如1 2 3 4 … n那么这个dp的话,复杂度仍为O(n^2),于是继续优化。我们知道如果一个一个涂,那么需要花费n。所以最优方案不能大于n,也就是不能连着sqrt(n)个不同的颜色一起涂,否则代价大于n了,这里进行剪枝。复杂度降为O(nsqrt(n)),还是可以接受的。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 50010;
const int inf = 0x3f3f3f3f;

int a[maxn], pre[maxn], nxt[maxn], dp[maxn];
map<int, int> mp;

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            pre[i] = i - 1;
            nxt[i] = i + 1;
        }

        mp.clear();
        memset(dp, 0x3f, sizeof(dp));
        dp[0] = 0, pre[0] = -1;
        for (int i = 1; i <= n; i++) {
            if (!mp.count(a[i])) mp[a[i]] = i;
            else {
                int id = mp[a[i]];
                nxt[pre[id]] = nxt[id];
                pre[nxt[id]] = pre[id];
                mp[a[i]] = i;
            }

            int cnt = 0;
            for (int j = pre[i]; j != -1; j = pre[j]) {
                cnt++;
                dp[i] = min(dp[i], dp[j] + cnt * cnt);
                if (cnt * cnt > i)
                    break;
            }
        }

        printf("%d\n", dp[n]);
    }
    return 0;
}

 

Latest posts by 青鸟千秋 (see all)

CF-1025D Recovering BST(区间dp)

传送门 题意:给定n个整数,问是否能生成一棵BST(二分查找树,左子树都比它小,右子树都比它大),并且有边相连的点权的gcd>1。 思路:区间dp,dp[l][...

阅读全文

牛客网暑期多校第五场E room(费用流)

传送门 题意:有n个宿舍,每个宿舍住4个人,给定去年n个宿舍的人员构成,今年n个4人组合的情况,求最少几个人需要搬寝室。 思路:转化为最小费用最大流解...

阅读全文

HDU-4091 Zombie’s Treasure Chest(暴力)

传送门 题意:有一个容量为n的箱子,和无限多的两种珠宝,体积和价值分别是s1,v1,s2,v2,求能装下的最大价值。 思路:直接暴力枚举会TLE,先计算s1 s2的LC...

阅读全文

欢迎留言