一串首尾相连的珠子(m个),有N种颜色(N《=10),设计一个算法,取出其中一段,要求包含所有N中颜色,并使长度最短。并分析时间复杂度与空间复杂度。
真是不好做唉。。和一般的DP不是很一样。做了很久了。一直不是十分能想通,最后的代码写的也很繁复,不简练。
- /*
- * =====================================================================================
- *
- * Filename: bead.c
- *
- * Description:
- *
- * Version: 1.0
- * Created: 10/20/2012 11:46:48 AM
- * Revision: none
- * Compiler: gcc
- *
- * Author: royn.wang.renyuan@gmail.com (),
- * Organization:
- *
- * =====================================================================================
- */
- #include <stdlib.h>
- #include <stdio.h>
- #define MAXK 10
- #define MAXM 100 /* */
- int getfirstvalue(int *input,int n){
- int match = (1<<n)-1;
- int end = -1;
- int v = 0;
- do{
- end++;
- v |= 1<<input[end];
- }while(v!=match);
- return end;
- }
- int getnextoccur(int tarindex, int *input, int size){
- int i;
- for(i = tarindex+1;i<size*2;i++){
- if( input[i%size] == input[tarindex])
- return i%size;
- }
- return -1;
- }
- /*
- * === FUNCTION ======================================================================
- * Name: main
- * Description:
- * =====================================================================================
- */
- int
- main ( int argc, char *argv[] )
- {
- int input[] = {0,1,2,3,4,4,5,4,2,3,1,0,2,3};
- int n = 6;
- int size = sizeof(input)/sizeof(int);
- int next[size];
- int end[size];
- int i = 0;
- end[0] = getfirstvalue(input,n);
- int minlen = end[0];
- for(;i<size;i++){
- next[i] = getnextoccur(i,input,size);
- }
- for(i = 1; i<size;i++){
- end[i] = end[i-1] ;
- if( (end[i]>i && (next[i-1] < i || next[i-1]>end[i]))
- ||
- (end[i]<i && next[i-1] > end[i] && next[i-1]<i)
- ){
- end[i] = next[i-1];
- }
- printf ( "start = %d end = %d\n", i,end[i] );
- int tmp = end[i]>i?end[i]-i+1 : size-i+end[i];
- minlen = tmp>minlen?minlen:tmp;
- }
- printf ( "min length = %d\n", minlen );
- return EXIT_SUCCESS;
- } /* ---------- end of function main ---------- */
阅读(103) | 评论(0) | 转发(0) |