1171.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 38 行

#include<iostream>
#include<string>
using namespace std;
int c1[250001],c2[250001];
void main()
{
    int n,v[51],m[51];
    while(cin>>n&&n>=0){
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        memset(v,0,sizeof(v));
        memset(m,0,sizeof(m));
        int i,j,k,total,mean;
        total=0;
        for(i=0;i<n;i++){
            cin>>v[i]>>m[i];
            total+=v[i]*m[i];
        }
        c1[0]=1;
        for(i=0;i<n;i++){
            for(j=0;j<=total;j++)
                if(c1[j])
                    for(k=0;k<=m[i];k++)
                        if(v[i]*k+j<=total)
                            c2[v[i]*k+j]+=c1[j];
            for(j=0;j<=total;j++){
                c1[j]=c2[j];
                c2[j]=0;
            }
        }
        mean=total/2;
        for(i=mean;i>=0;i--)
            if(c1[i])
                break;
        cout<<total-i<<" "<<i<<endl;
    }
}