#include<iostream.h> 
#include<fstream.h> 
#include<stdlib.h> 
#include<algorithm> 

ifstream in("in.txt"); 
//#define cin in 

struct datatype{ 
    int total; 
    int a[20]; 
}; 

datatype a[1000],b[1000]; 
datatype *p,*q; 

struct datasave{ 
    int minus; 
    int total; 
}; 

datasave data[200]; 

int n,m; 

void clear(datatype *p){ 
    int i; 
    for(i=0;i<=40*m;i++) 
        p[i].total=0; 
} 

void input(){ 
    cin>>n>>m; 
    if(n==0&&m==0)exit(0); 
    int i; 
    for(i=0;i<n;i++){ 
        int a,b; 
        cin>>a>>b; 
        data[i].minus=a-b+20; 
        data[i].total=a+b+20; 
    } 
    clear(a); 
    for(i=0;i<n;i++){ 
        int x=data[i].minus; 
        if(a[x].total<data[i].total){ 
            a[x].total=data[i].total; 
            a[x].a[0]=i; 
        } 
    } 
} 

int temp[200]; 
void filltemp(int* a,int k){ 
    int i; 
    for(i=0;i<n;i++) 
        temp[i]=0; 
    for(i=0;i<k;i++) 
        temp[a[i]]=1; 
} 

void print(datatype* p,int k){ 
    static time=1; 
    //cout<<n<<endl;/// 
    cout<<"Jury #"<<time++<<endl; 
    int x=p[k].total-20*m; 
    int y=k-20*m; 
    cout<<"Best jury has value "<<(x+y)/2; 
    cout<<" for prosecution and value "<<(x-y)/2; 
    cout<<" for defence:"<<endl; 
    std::sort(p[k].a,p[k].a+m); 
    int i; 
    for(i=0;i<m;i++) 
        cout<<' '<<p[k].a[i]+1; 
    cout<<endl<<endl; 
} 

void solve(){ 
    p=a;q=b; 
    int i,j,k; 
    for(i=1;i<m;i++){ 
        clear(q); 
        for(j=0;j<=40*i;j++){ 
            if(p[j].total==0)continue; 
            filltemp(p[j].a,i); 
            for(k=0;k<n;k++){ 
                if(temp[k]==1)continue; 
                int x=data[k].minus; 
                int y=j+x; 
                if(q[y].total<p[j].total+data[k].total){ 
                    q[y].total=p[j].total+data[k].total; 
                    std::copy(p[j].a,p[j].a+i,q[y].a); 
                    q[y].a[i]=k; 
                } 
            } 
        } 
        std::swap(p,q); 
    } 
    for(i=0;;i++){     
        if(p[20*m+i].total==0){ 
            if(p[20*m-i].total==0)continue; 
            else{ 
                print(p,20*m-i); 
                break; 
            } 
        } 
        else{ 
            if(p[20*m-i].total==0) 
                print(p,20*m+i); 
            else{ 
                if(p[20*m+i].total>p[20*m-i].total) 
                    print(p,20*m+i); 
                else print(p,20*m-i); 
            } 
            break; 
        } 
    } 
} 

void main(){ 
    while(1){ 
        input(); 
        solve(); 
    } 
} 

• Re:这题递推运算量好像很可能上亿啊！递归内存不允许啊！！！咋办！！！ (435) bxsj 2007-11-04 11:02:14
• Re:这题递推运算量好像很可能上亿啊！递归内存不允许啊！！！咋办！！！ (406) center1370 2012-05-11 17:15:28