## poj 1010 STAMPS

2019年02月10日 算法 ⁄ 共 2649字 ⁄ 字号 评论关闭
```#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;
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()
{