首页 > 代码库 > hdu5009

hdu5009

2024-07-22 19:54:31   220人阅读

这题说的是给了一个  长度为n(n<=50000)的数列数列表示的是给每个珍珠涂的颜色然后你可以操至多n次 每次操作只能操作连续的区间然后 每次操作是的代价是这个区间的 不同颜色的个数，

可以知道最多的代价是n 然后 可以知道当这个区间内不同颜色的个数大于sqrt(n) 时才进行合并 否者 就是一个一个涂这样代价少的多，然后现在就剩下处理在当前位置j种颜色的达到的最远距离然后就 找到这个点的前一个相同的位置per[i]

然后可以知道 f[i][j] = per[i]>i-1-flow[i-1][j]?flow[i-1][j]+1 :flow[i-1][j-1]+1  当这个 点重复点出在前面那个点（i-1）j种不同的最远距离内 ，那么就知道他一定与前面某个相同，然后如果小于可以知道在 i-1位置的j-1种在加上当前的距离1 就得到了现在的 j种的当前位置

#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>#include <vector>#include <cmath>using namespace std;const int maxn =10005*5;int A[maxn],B[maxn];int F[maxn],per[maxn];int flow[2][maxn];int dp[maxn];int main(){     int n;     while(scanf("%d",&n)==1){         for(int i=1; i<=n; i++){               scanf("%d",&A[i]);               B[i-1]=A[i];         }         sort(B,B+n);         int len = unique( B, B+n )-B;         for(int i=1; i<=n; i++){             A[i]= lower_bound(B,B+len,A[i])-B;         }         memset(F,-1,sizeof(F));         int m=2;         for(int i=2; i<=n; ++i){             if(A[m-1]!=A[i]){                 A[m++]=A[i];             }         }         for(int i=1 ; i<m; ++i){              per[i]=F[A[i]];              F[A[i]]=i;         }         memset(flow,0,sizeof(flow));         int now=0;         int L =sqrt(m+1.0);         for(int i=1; i<m; ++i){                dp[i]=i;            now=1-now;            for(int j=1; j<=L; ++j){             flow[now][j]=per[i]>i-1-flow[1-now][j]?flow[1-now][j]+1:flow[1-now][j-1]+1;             dp[i]=min(dp[i],j*j+dp[i-flow[now][j]]);            }         }         printf("%d\n",dp[m-1]);     }    return 0;}
View Code

 

hdu5009


联系
我们