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

100题1A留念,排序 +多重背包79MS贴代码

Posted by 448501561 at 2014-08-16 15:38:11 on Problem 2392
#include<iostream>
#include<cstring>
using namespace std;

bool dp[40001];
int count[40001];
int n,h[401],a[401],c[401];

int Sort(int *a,int left,int right)
{
    int temp=a[left];
    int H=h[left];
    int C=c[left];
    while(left<right)
    {
        while(a[right]>temp&&left<right)
            right--;

        if(left<right)
        {
            a[left]=a[right];
            h[left]=h[right];
            c[left]=c[right];
            left++;
        }
        while(a[left]<temp&&left<right)
            left++;
        if(left<right)
        {
            a[right]=a[left];
            h[right]=h[left];
            c[right]=c[left];
            right--;
        }
    }
    a[left]=temp;
    h[left]=H;
    c[left]=C;
    return left;
}

void QuickSort(int *a,int left,int right)
{
    int q;
    if(left<right)
    {
        q=Sort(a,left,right);
        QuickSort(a,left,q-1);
        QuickSort(a,q+1,right);
    }

}

int main()
{
    cin>>n;
    int i,j;
    for(i=1;i<=n;i++)
        cin>>h[i]>>a[i]>>c[i];
    QuickSort(a,1,n);

    memset(dp,0,sizeof(dp));
    dp[0]=1;
    for(i=1;i<=n;i++)
    {
        memset(count,0,sizeof(count));
        for(j=h[i];j<=a[i];j++)
        {
            if(dp[j-h[i]]&&count[j-h[i]]<c[i]&&!dp[j])
            {
                dp[j]=1;
                count[j]=count[j-h[i]]+1;
            }
        }
    }
    for(i=a[n];i>=0;i--)
        if(dp[i])
            break;
    cout<<i<<endl;
    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