> #include "iostream"
> 
> using namespace std;
> 
> char color[11][11];
> int colothes[11][101];
> int num_colothes[11];
> char temp[11];
> int dp[101][100001];
> 
> int minimum (const void *a,const void *b)
> {
>     return *(int *)a-*(int *)b;
> }
> 
> 
> int main ()
> {
>     int i,j,k;
>     int n,m;
>     int num;
>     int sum,total,max;
>     int temp1;
>     //freopen("in1.txt","r",stdin);
>     for(;scanf("%d%d",&n,&m)!=EOF;)
>     {
>         if(n==0 && m==0 ) return 1;
> 
>         for(i=0;i<n;i++)
>             scanf("%s",color[i]);
> 
>         memset(num_colothes,0,sizeof(num_colothes));
> 
>         for(i=0;i<m;i++)
>         {
>             scanf("%d %s",&num,temp);
>             for(j=0;j<n;j++)
>                 if(strcmp(temp,color[j])==0)
>                     break;
>                 colothes[j][ num_colothes[j]++ ] = num;
>         }
>         /*
>         for(i=0;i<n;i++)
>         {
>             qsort( colothes[i] , num_colothes[i] , sizeof(int) , minimum);
>         }*/
> 
>         total=0;
>         
>         for(i = 0; i < n ;i++)
>         {
>             if(num_colothes[i]==0) continue;
> 
>             sum=0;
> 
>             for(j=0 ; j< num_colothes[i] ;j++)
>                 sum+=colothes[i][j];
> 
>             memset(dp,0,sizeof(dp));
>             
>             for(j=0;j<=num_colothes[i];j++)
>                 dp[j][0]=1;
> 
>             max=0;
>             temp1=0;
>             
>             for(j=1;j<=num_colothes[i];j++)
>             {                
>                 for( k = colothes[i][j-1] ; k<=sum/2 /*&& k<= temp1*/ ;k++ )
>                 {
>                     /*
>                     if(dp[ j-1 ][ k ]!=1 ) continue; 
>                     dp[ j ][ k + colothes[ i ][ j-1 ] ] = 1 ;
> 
>                     if(k + colothes[ i ][ j-1 ] >max)
>                             max=k + colothes[ i ][ j-1 ];*/
>                     if(dp[j-1][ k-colothes[i][j-1] ]==1)
>                     {
>                         if(k>max)
>                             max=k;
>                         dp[ j ][ k ] = 1 ;
>                     }
>                 }
>                 //temp1 += colothes[i][j-1] ;
>             }
>             total+=sum-max;
>             
>         }
>         printf("%d\n",total);
>     }
>     return 1;
> }

• Re:Why TLE ? Give me a reason !!!!! I just test n^2 times ! You can tell me? (31) units 2007-04-28 12:16:47