首页 > 代码库 > HDU 5009 Paint Pearls(西安网络赛C题) dp+离散化+优化
HDU 5009 Paint Pearls(西安网络赛C题) dp+离散化+优化
转自:http://blog.csdn.net/accelerator_/article/details/39271751
吐血ac。。。
11668627 | 2014-09-16 22:15:24 | Accepted | 5009 | 1265MS | 1980K | 2290 B | G++ | czy |
Paint PearlsTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1473 Accepted Submission(s): 466Problem Description Lee has a string of n pearls. In the beginning, all the pearls have no color. He plans to color the pearls to make it more fascinating. He drew his ideal pattern of the string on a paper and asks for your help. In each operation, he selects some continuous pearls and all these pearls will be painted to their target colors. When he paints a string which has k different target colors, Lee will cost k2 points. Now, Lee wants to cost as few as possible to get his ideal string. You should tell him the minimal cost. Input There are multiple test cases. Please process till EOF. For each test case, the first line contains an integer n(1 ≤ n ≤ 5×104), indicating the number of pearls. The second line contains a1,a2,...,an (1 ≤ ai ≤ 109) indicating the target color of each pearl. Output For each test case, output the minimal cost in a line. Sample Input 31 3 3103 4 2 4 4 2 4 3 2 2 Sample Output 27 Source 2014 ACM/ICPC Asia Regional Xi‘an Online Recommend hujie | We have carefully selected several similar problems for you: 5017 5016 5014 5013 5011 |
转自:http://blog.csdn.net/accelerator_/article/details/39271751
题意:给定一个目标颜色,每次能选一个区间染色,染色的代价为这个区间不同颜色数的平方,问最小代价
思路:先预处理,把相同颜色的一段合并成一个点,然后把颜色离散化掉,然后进行dp,dp[i]表示染到第i个位置的代价,然后往后转移,转移的过程记录下不同个数,这样就可以转移了,注意加个剪枝,就是如果答案大于了dp[n]就不用往后继续转移了
哎,dp思路还是很混乱,有空还要把这题好好做做。。。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<map> 9 #include<string> 10 11 #define N 50005 12 #define M 15 13 #define mod 10000007 14 #define p 10000007 15 #define mod2 100000000 16 #define ll long long 17 #define LL long long 18 #define maxi(a,b) (a)>(b)? (a) : (b) 19 #define mini(a,b) (a)<(b)? (a) : (b) 20 21 using namespace std; 22 23 int n,k,s; 24 int a[N]; 25 int b[N]; 26 map<int,int>c; 27 int vis[N]; 28 int dp[N]; 29 int cou; 30 vector<int>save; 31 32 void ini() 33 { 34 //memset(vis,0,sizeof(vis)); 35 memset(dp,0x3f3f3f3f,sizeof(dp)); 36 c.clear(); 37 k=0; 38 int i; 39 scanf("%d",&a[1]); 40 k=1; 41 b[1]=a[1]; 42 for(i=2;i<=n;i++){ 43 scanf("%d",&a[i]); 44 if(a[i]!=a[i-1]){ 45 k++; 46 b[k]=a[i]; 47 } 48 } 49 s=0; 50 for(i=1;i<=k;i++){ 51 if(c[ b[i] ]==0){ 52 // vis[ b[i] ]=1; 53 s++; 54 c[ b[i] ]=s; 55 } 56 } 57 58 for(i=1;i<=k;i++){ 59 b[i]=c[ b[i] ]; 60 // dp[i]=i; 61 } 62 // for(i=1;i<=k;i++){ 63 // printf(" i=%d b=%d\n",i,b[i]); 64 //} 65 66 } 67 68 void solve() 69 { 70 int i,j; 71 dp[0]=0; 72 dp[k]=k; 73 for(i=0;i<k;i++){ 74 cou=0; 75 // vis[ b[i] ]=1; 76 //save.push_back(b[i]); 77 for(j=i+1;j<=k;j++){ 78 // if(cou*cou>=k) break; 79 if(vis[ b[j] ]==0 ){ 80 vis[ b[j] ]=1; 81 save.push_back(b[j]); 82 cou++; 83 } 84 if (dp[i] + cou * cou >= dp[k]) break; 85 // printf(" i=%d j=%d dpj=%d cou=%d dp=%d ",i,j,dp[j],cou,dp[i]+cou*cou); 86 dp[j]=min(dp[j],dp[i]+cou*cou); 87 // printf(" dpj=%d\n",dp[j]); 88 } 89 for(vector<int>::iterator it=save.begin();it!=save.end();it++){ 90 vis[*it]=0; 91 } 92 save.clear(); 93 } 94 } 95 96 void out() 97 { 98 //for(int i=1;i<=k;i++){ 99 // printf(" i=%d dp=%d\n",i,dp[i]);100 //}101 printf("%d\n",dp[k]);102 }103 104 int main()105 {106 //freopen("data.in","r",stdin);107 //freopen("data.out","w",stdout);108 //scanf("%d",&T);109 //for(int cnt=1;cnt<=T;cnt++)110 // while(T--)111 while(scanf("%d",&n)!=EOF)112 {113 ini();114 solve();115 out();116 }117 118 return 0;119 }
HDU 5009 Paint Pearls(西安网络赛C题) dp+离散化+优化
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。