题目链接：hdu 5009 Paint Pearls

题目大意：给定一串珠子的目标颜色，现在要为这些珠子上色，每次可以选中一段区间上的珠子上色，代价为这段区间中颜色的数量k的平方，要求用最少的代价。

解题思路：dp[i]表示到i的最优代价，加上优化即可，当k（颜色总数）的平方大于N的可以直接跳出循环，当dp[i] > dp[i+1]时，可以考虑直接从dp[i+1]转移。
现场的时候交C++ TLE了，不然这题应该很快就出了，到最后交G++才过也是醉了。。。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; const int maxn = 5 * 1e4 + 5; const int INF = 0x3f3f3f3f; struct point { int val, pos; point (int val = 0, int pos = 0) { this->val = val; this->pos = pos; } }p[maxn]; inline bool sort_val (const point& a, const point& b) { return a.val < b.val; } inline bool sort_pos (const point& a, const point& b) { return a.pos < b.pos; } int N, M, v[maxn]; void init () { M = N; for (int i = 1; i <= N; i++) scanf("%d", &p[i].val); int mv = 1; for (int i = 2; i <= N; i++) { if (p[i].val != p[i-1].val) { p[++mv] = p[i]; p[mv].pos = mv; } } N = mv; sort(p + 1, p + 1 + N, sort_val); mv = 0; int pre = -1; for (int i = 1; i <= N; i++) { if (p[i].val != pre) { pre = p[i].val; mv++; } p[i].val = mv; } sort(p + 1, p + 1 + N, sort_pos); } int dp[maxn], vis[maxn]; int solve () { if (N + 3 >= M) return N; vector
       
         vec; memset(dp, INF, sizeof(dp)); dp[0] = 0; dp[N] = N; int mv = 0; while (true) { int u = mv; if (u == N) return dp[u]; int cnt = 0, ans = dp[u + 1]; mv = u + 1; for (int i = u + 1; i <= N; i++) { if (vis[p[i].val] == 0) { cnt++; vis[p[i].val] = 1; vec.push_back(p[i].val); } if (cnt * cnt + dp[u] > dp[N]) break; if (dp[i] > dp[u] + cnt * cnt) dp[i] = dp[u] + cnt * cnt; if (dp[i] <= ans) { ans = dp[i]; mv = i; } } for (int i = 0; i < cnt; i++) vis[vec[i]] = 0; vec.clear(); } return N; } int main () { while (scanf("%d", &N) == 1) { init(); printf("%d\n", solve()); } return 0; }