学步园

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>

using namespace std;

const int INF = 0x7fffffff;

struct Comb{
    int sumConsist , sumType;
    int Consist[ 5 ] , Type[ 5 ];
    int Highest;
    bool tie;
    Comb(){
        tie = false;
        sumConsist = sumType = Highest = 0;
    }
    friend bool operator == ( Comb a , Comb b ){
        if( a.sumType != b.sumType || a.sumConsist != b.sumConsist || a.Highest != b.Highest ) return false;
        for( int i = 0; i < 4; i ++ )
            if( a.Consist[ i ] != b.Consist[ i ] || a.Type[ i ] != b.Type[ i ] ) return false;
        return true;
    }
    friend bool operator < ( Comb a , Comb b ){
        if( a.sumType == b.sumType ){
            if( a.sumConsist == b.sumConsist ) return a.Highest < b.Highest;
            return a.sumConsist > b.sumConsist;
        }
        return a.sumType < b.sumType;
    }
};
int Stamps[ 100 ], CustomerRequests[ 100 ];
int sumStamp, sumCustomer;
map< int , int > Pus;
map< int , int >::iterator It;
bool read(){
    sumCustomer = sumStamp = 0;
    int tmp;
    while( true ){
        if( scanf( "%d" , &tmp ) != EOF ){
			It = Pus.find( tmp );
			if( It == Pus.end() ){
				Pus[ tmp ] = 1;
				Stamps[ sumStamp ++ ] = tmp;
			}
			else
			{
				if( It->second < 4 ) {Pus[ tmp ] ++;Stamps[ sumStamp ++ ] = tmp; }
			}
            if( tmp == 0 ) break;
        }else return false;
    }
    Pus.clear();
    while( scanf("%d" , &CustomerRequests[ sumCustomer ++ ]) , CustomerRequests[ sumCustomer - 1 ] != 0 );
    return true;
}
map< int , Comb > Ans;
map< int , Comb >::iterator Pos;
void InitAns(){
    int cnt;
    Comb Tmp;
    for( cnt = 0; cnt < sumCustomer; cnt ++ ) Ans[ CustomerRequests[ cnt ] ] = Tmp;
}
bool IsSameVal( Comb a, Comb b )
{
	return a.sumType == b.sumType && a.sumConsist == b.sumConsist && a.Highest == b.Highest;
}
void dfs( int Sum , int cnt, int * Member, int * Type ){
    if( cnt == 4 ){
        Pos = Ans.find( Sum );
        if( Pos == Ans.end() ) return ;
        Comb Tmp;
        int END = sumStamp-1;
        for( int i = 0; i < 4; i ++ )
        {
            Tmp.Consist[ i ] = Member[ i ];
            Tmp.Type[ i ] = Type[ i ];
        }
        sort( Tmp.Consist, Tmp.Consist+4 );
        sort( Tmp.Type, Tmp.Type+4);
        Tmp.sumConsist = Tmp.sumType = 4;
        for( int i= 3; i >=0; i -- )
        {
            if( Tmp.Consist[ i ] == INF ) Tmp.sumConsist --;
            else Tmp.Highest = max( Tmp.Highest , Tmp.Consist[ i ] );
            if( i != 0 ) if( Tmp.Type[ i ] == END || Tmp.Type[ i ] == Tmp.Type[ i -1 ] ) Tmp.sumType --;
            if( i == 0 && Tmp.Type[ i ] == END ) Tmp.sumType --;
        }
        if( Tmp.sumConsist == 0 || Tmp.sumType == 0 ) return ;
        if( Tmp == Pos->second ) return ;
        if( Pos->second < Tmp ) Pos->second = Tmp;
        else{
			if( IsSameVal( Tmp, Pos->second ) ) Pos->second.tie = true;
        }
        return ;
    }
    for( int i = 0; i < sumStamp; i ++ ){
        Member[ cnt ] = ( i == sumStamp - 1 ? INF : Stamps[ i ] );
        Type[ cnt ] = i;
        dfs( Sum+Stamps[i] , cnt+1 , Member , Type );
    }

}

void Print(){

	for( int i = 0; i < sumCustomer-1; i ++ ){
		int ID = CustomerRequests[ i ];
		Comb& Tmp = Ans[ ID ];
		if( Tmp.sumType == 0 ) printf("%d ---- none\n", ID );
		else if( Tmp.tie ) printf("%d (%d): tie\n", ID , Tmp.sumType );
		else{
			printf( "%d (%d):",  ID , Tmp.sumType );
			for( int i = 0; i < Tmp.sumConsist; i ++ )
				printf(" %d", Tmp.Consist[ i ]);
			printf("\n");
		}

	}
}
void slove(){
    InitAns();
    int Member[ 5 ] , Type[ 5 ];
    dfs( 0, 0, Member, Type );
    Print();
    Ans.clear();
}
int main()
{
    while( read() ) slove();
    return 0;
}

一直 TLE， 知道看到 ddiscuss 里 一个同学说的神剪枝， 如果相同价值的邮票超过 4 个， 就不用再加进去了， 说这样的话能从TLE到16MS， 我用了这个加上之前自己的一个剪枝 ，0MS过了 如果 一个组合的值不在顾客需求的几何内，那么就没有必要计算了。

附上代码