#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? (2408) units 2007-04-28 12:15:35
  • 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
• Re:Why TLE ? Give me a reason !!!!! I just test n^2 times ! You can tell me? (2408) Knight_of_Night 2007-05-22 20:12:57