本文主要是介绍HDU 5009 Paint Pearls（西安网络赛C题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 5009 Paint Pearls
题目链接
题意：给定一个目标颜色，每次能选一个区间染色，染色的代价为这个区间不同颜色数的平方，问最小代价
思路：先预处理，把相同颜色的一段合并成一个点，然后把颜色离散化掉，然后进行dp，dp[i]表示染到第i个位置的代价，然后往后转移，转移的过程记录下不同个数，这样就可以转移了，注意加个剪枝，就是如果答案大于了dp[n]就不用往后继续转移了
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;const int N = 50005;int n, vis[N];
vector<int> save;struct Point {int val, id, rank;
} p[N];bool cmpv(Point a, Point b) {return a.val < b.val;
}bool cmpid(Point a, Point b) {return a.id < b.id;
}const int INF = 0x3f3f3f3f;int dp[N];int main() {while (~scanf("%d", &n)) {for (int i = 1; i <= n; i++)scanf("%d", &p[i].val);int pn = 1;for (int i = 2; i <= n; i++) {if (p[i].val != p[i - 1].val)p[++pn] = p[i];}n = pn;for (int i = 1; i <= n; i++)p[i].id = i;sort(p + 1, p + n + 1, cmpv);p[1].rank = 0;int s = 0;for (int i = 2; i <= n; i++) {if (p[i].val != p[i - 1].val)++s;p[i].rank = s;}sort(p + 1, p + n + 1, cmpid);memset(dp, INF, sizeof(dp));dp[0] = 0;dp[n] = n;for (int i = 0; i < n; i++) {int cnt = 0;if (dp[i] > dp[i + 1]) continue;for (int j = i + 1; j <= n; j++) {if (vis[p[j].rank] == 0) {save.push_back(p[j].rank);cnt++;}vis[p[j].rank]++;if (dp[i] + cnt * cnt >= dp[n]) break;dp[j] = min(dp[j], dp[i] + cnt * cnt);}for (int i = 0; i < save.size(); i++)vis[save[i]] = 0;save.clear();}printf("%d\n", dp[n]);}return 0;
}这篇关于HDU 5009 Paint Pearls（西安网络赛C题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
