缩点,把连续的相同的颜色用一个代替,方便后续操作。
DP+剪枝,dp[i]表示染色到第i个珠子时的最优方案数
因为dp[i]的最坏情况是i(i个都不相同,需要1^2+1^2+...+1^2=i个points)
这一题RE WA了好久。。。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> using namespace std; //hdu 5009 int n; const int maxn=50100; int a[maxn]; int vis[maxn]; int dp[maxn]; class point { public: int idx; int val; int rak; point(){} point(int i,int v,int r) { idx=i; val=v; rak=r; } }; point p[maxn]; bool cmpval(point p1, point p2) { return p1.val<p2.val; } bool cmpidx(point p1, point p2) { return p1.idx<p2.idx; } void input() { memset(dp,0,sizeof(dp)); memset(vis,0,sizeof(vis)); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } p[1].val=a[1]; p[1].idx=1; int ct=1; for(int i=2;i<=n;i++) { if(a[i]!=a[i-1]) { p[++ct].val=a[i]; p[ct].idx=ct; } } n=ct; // for(int i=0;i<=ct;i++) cout<<p[i].val<<" "; // cout<<endl; for(int i=1;i<=n;i++) p[i].idx=i; sort(p+1,p+n+1,cmpval); int s=1; p[1].rak=1; for(int i=2;i<=n;i++) //重新编号省空间,之前直接O(1) vis[p[i].val]判断是否访问过然后RE了,因为val最大会达到10^9 { if(p[i].val!=p[i-1].val) { s++; } p[i].rak=s; } sort(p+1,p+n+1,cmpidx); for(int i=0;i<=n;i++) { dp[i]=i;//i个颜色都不同时,1^2+1^2+1^2..+1^2 } //vector<int >str; dp[n+1]=-1; vector<int>save; for(int i=0;i<n;i++)//i从1开始结果WA了,因为这样考虑划分时是从[1,1]-[2,j]考虑的,[1,j]的划分就没有包含在内 { int cnt=0; if(dp[i]>dp[i+1]) continue; for(int j=i+1;j<=n;j++) { //int tmp=p[j].val; int tmp=p[j].rak; if(vis[tmp]==0) { save.push_back(tmp); cnt++; } vis[tmp]++; if(dp[i]+cnt*cnt>=dp[n]) break;//再往后找不同的只会更多 dp[j]=min(dp[j],dp[i]+cnt*cnt); } for(int j=0;j<save.size();j++) { vis[save[j]]=0; } //memset(vis,0,sizeof(vis)); 会TLE save.clear(); } printf("%d\n",dp[n]); } int main() { freopen("input.txt","r",stdin); // freopen("data.txt","r",stdin); // freopen("out1.txt","w",stdout); while(scanf("%d",&n)!=EOF) { input(); } return 0; }