hawking.cpp

这是一道典型的动态规划题 提供了三种方法(用C++代码实现)

/* 
by hawking@pku 
*/ 
#include<iostream.h> 
#include<search.h> 
#include<memory.h> 
const int MAX_STAMP_TYPES =100; 
const int MAX_TOT_VALUE = 100; 
const int MAX_CUSTOMER=100; 
int s[MAX_STAMP_TYPES],s_size,cus[MAX_CUSTOMER],c_size,maxc,count[100]; 
bool custom[MAX_TOT_VALUE];     
class Combine{ 
public: 
    int tot; 
    int ts;//types of stamps 
    int f;//flag 1 can 2 tie,0 can't 
    int s[4];//each stamps used here 
    int sc;//used stamps number 
    int max;//single maxed stamp value; 
public: 
    bool isHave(int type){ 
        for(int i=0;i<sc;i++) 
            if(s[i]==type)return true; 
        return false; 
    } 
    void findMax(){ 
        max=0; 
        for(int i=0;i<sc;i++) 
            if(::s[s[i]]>max)max=::s[s[i]]; 
    } 
    void addStamp(int type){ 
        if(!isHave(type))ts++; 
        s[sc++]=type; 
        tot+=::s[type]; 
        if(::s[type]>max)max=::s[type]; 
    } 
    void removeLastStamp(int type){ 
        sc--; 
        if(!isHave(type))ts--; 
        tot-=::s[type]; 
        findMax(); 
    }         
}currCus[MAX_TOT_VALUE],c; 
int com(const void * a,const void *b) 
{ 
    return *((int *)a)-*((int*)b); 
} 
void init() 
{ 
    maxc=c_size=s_size=0; 
    memset(custom,0,MAX_TOT_VALUE*sizeof(bool)); 
    memset(count,0,100*sizeof(int)); 
} 
bool read() 
{ 
    init(); 
    int t; 
    cin>>t; 
    if(!cin)return false; 
    while(t!=0){ 
        if(count[t]++<5)s[s_size++]=t; //modify by duoshute here
        cin>>t; 
    } 
    qsort(s,s_size,sizeof(int),com); 
    cin>>t; 
    while(t!=0){ 
        cus[c_size++]=t; 
        custom[t]=true; 
        if(t>maxc)maxc=t; 
        cin>>t; 
    } 
    return true; 
} 
int a[4],b[4]; 
bool same(int *t1,int *t2,int n) 
{ 

    memcpy(a,t1,n*sizeof(int)); 
    memcpy(b,t2,n*sizeof(int)); 
/*    qsort(a,n,sizeof(int),com);           //omited by duoshute
    qsort(b,n,sizeof(int),com); */
    return memcmp(a,b,n*sizeof(int))==0; 
} 
void solve(int ss,int last) //int last is added by duoshute 
{ 
    if(custom[c.tot]) 
    { 
        if(!currCus[c.tot].f 
                ||c.ts>currCus[c.tot].ts 
                ||c.ts==currCus[c.tot].ts&&c.sc<currCus[c.tot].sc 
                ||c.ts==currCus[c.tot].ts&&c.sc==currCus[c.tot].sc&&c.max>currCus[c.tot].max) 
        { 
            currCus[c.tot]=c; 
            currCus[c.tot].f=1; 
        } 
        else if(c.ts==currCus[c.tot].ts&&c.sc==currCus[c.tot].sc&&c.max==currCus[c.tot].max) 
        { 
            if(!same(c.s,currCus[c.tot].s,c.sc)) 
                currCus[c.tot].f=2; 
        } 
             
    } 
    if(c.sc>=4||c.tot>maxc)return; 
    for(int i=last;i<s_size;i++)  
    { 
        c.addStamp(i); 
        solve(ss+1,i); 
        c.removeLastStamp(i); 
    } 
} 
void main() 
{ 
    while(read()) 
    { 
        memset(&c,0,sizeof(Combine)); 
        memset(currCus,0,MAX_TOT_VALUE*sizeof(Combine)); 
        solve(0,0); 
        for(int i=0;i<c_size;i++) 
            if(currCus[cus[i]].f==0) 
                cout<<cus[i]<<" ---- none"<<endl; 
            else if(currCus[cus[i]].f==2) 
                cout<<cus[i]<<" ("<<currCus[cus[i]].ts<<"): "<<"tie"<<endl; 
            else  
            { 
                cout<<cus[i]<<" ("<<currCus[cus[i]].ts<<"):"; 
                qsort(currCus[cus[i]].s,currCus[cus[i]].sc,sizeof(int),com); 
                for(int j=0;j<currCus[cus[i]].sc;j++) 
                    cout<<' '<<s[currCus[cus[i]].s[j]]; 
                cout<<endl; 
            } 
    } 
}