Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

qsort WA sort AC 求解释,附170+MS代码

Posted by speedcell4 at 2011-10-10 00:22:27 on Problem 2392
#include<iostream>
#include<algorithm>

using namespace std;

const int MAXN = 40012;

int n,cnt;
bool dp[MAXN];
int h[MAXN],a[MAXN],c[MAXN],r[MAXN];

void ZeroOne_Pack(int w,int v)
{
    for(int i=v;i>=w;i--) if(dp[i-w]) dp[i]=true,cnt=max(cnt,i);
}
void Complete_Pack(int w,int v)
{
    for(int i=w;v>=i;i++) if(dp[i-w]) dp[i]=true,cnt=max(cnt,i);
}
void Multiple_Pack(int w,int n,int v)
{
    if(w*n>=v) Complete_Pack(w,v);
    else
    {
        for(int i=1;i<n;i*=2)
        {
            n-=i;
            ZeroOne_Pack(i*w,v);
        }
        ZeroOne_Pack(n*w,v);
    }
}
bool cmp(int i,int j)
{
    return a[i]<a[j];
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        cnt=0;
        int h_=0,a_=0,c_=0;
        memset(dp,false,sizeof(dp)); dp[0]=true;
        for(int i=0;n-i>0;i++)
        {
            scanf("%d %d %d",&h[i],&a[i],&c[i]);
            r[i]=i;
        }
        sort(r,r+n,cmp);
        for(int i=0;n-i>0;i++) Multiple_Pack(h[r[i]],c[r[i]],a[r[i]]);
        printf("%d\n",cnt);
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator