当前位置:编程学习 > C/C++ >>

TOJ 4283 Gifts with different style / 线段树 树状数组 背包

Gifts with different style
时间限制(普通/Java):1000MS/3000MS     运行内存限制:65536KByte
 
描述
 
 
前些日子GBQC国的小明在凤凰古城痛痛快快地玩了两天,临走之前希望给女友带回两件不同种类的纪念品,而且小明的背包最多只能容纳总体积不超过V的物品,各个纪念品使其女友的高兴程度的增加值也不全是一样的。
 
现在小明想知道,对于小明有有财力购买的N个纪念品,他需要买回哪两个才能使女友的高兴程度的增加值最大呢?
 
输入
 
 
输入包含多组测试数据。
 
对于每组测试数据,第一行包含三个整数N(1<=N<=10^5), C(1<=C<=10^4), V(1<=V<=10^4),其中N表示小明有财力购买的一共有N个纪念品,C表示市面上销售的纪念品一共可以分为C个种类,V表示小明的背包最多只能容纳体积不超过V的物品。接下来N行,每行用三个正整数i(1<=i<=C)、j
 
输出
 
 
对于每组测试数据,用一行输出一个整数表示小明最多可以让女友的高兴程度增加多少。如果小明没办法带回两件不同种类的纪念品,则输出“-1”(不包括引号)。
 
 
样例输入
 
2 3 5
1 2 3
2 4 1
3 3 5
1 2 4
1 2 5
3 3 2
样例输出
 
-1
7
树状数组功能找最大值
 
#include <stdio.h>  
#include <algorithm>  
#include <string.h>  
using namespace std;  
struct node  
{  
    int c;  
    int v;  
    int p;  
}a[100010];  
int n,c,v;  
int map[10010];  
  
bool cmp(node a,node b)  
{  
    return a.c < b.c;  
}  
int Lowbit(int t)   
{   
    return t & ( t ^ ( t - 1 ) );   
}   
int Sum(int end)   
{   
    int sum = 0;   
    while(end > 0)   
    {   
        if(sum < map[end])  
            sum = map[end];   
        end -= Lowbit(end);   
    }   
    return sum;   
}   
void update(int pos , int num)   
{   
    while(pos <= 10000)   
    {   
        if(map[pos] < num)  
            map[pos] = num;   
        pos += Lowbit(pos);   
    }   
}   
  
int main()  
{  
    int i,j,k,max;  
    while(scanf("%d %d %d",&n,&c,&v)!=EOF)  
    {  
        memset(map,0,sizeof(map));  
        max = 0;  
        for(i = 0;i < n; i++)  
            scanf("%d %d %d",&a[i].c,&a[i].v,&a[i].p);  
        sort(a,a+n,cmp);  
        for(i = 0,k = 0;i < n; i++)  
        {  
            if(i && a[i].c != a[i-1].c)  
            {  
                for(j = k; j < i; j++)  
                {  
                    update(a[j].v,a[j].p);  
                }  
                k = i;  
            }  
            int t = Sum(v - a[i].v);  
            if(t && a[i].p + t > max)  
                max = a[i].p + t;  
        }  
        if(max)  
            printf("%d\n",max);  
        else  
            puts("-1");           
    }  
    return 0;  
}  

 

 
下面是线段树
 
 
 
#include <stdio.h>  
#include <algorithm>  
#include <string.h>  
using namespace std;  
struct node  
{  
    int c;  
    int v;  
    int p;  
}b[100010];  
struct nod  
{  
    int l;  
    int r;  
    int num;  
}a[40010];  
bool cmp(node a,node b)  
{  
    return a.c < b.c;  
}  
int max(int x,int y)  
{  
    return x > y ? x : y;  
}  
void build(int l,int r,int rt)  
{  
    a[rt].l = l;  
    a[rt].r = r;  
    a[rt].num = 0;  
    if(l == r)  
        return ;  
    int m = (l + r) >> 1;  
    build(l,m,rt<<1);  
    build(m+1,r,rt<<1|1);  
}  
  
void update(int v,int p,int rt)  
{  
    if(a[rt].l == a[rt].r)  
    {  
        if(a[rt].num < p)  
            a[rt].num = p;  
        return;  
    }  
    int m = (a[rt].l + a[rt].r) >> 1;  
    if(v <= m)  
        update(v,p,rt<<1);  
    else  
        update(v,p,rt<<1|1);  
    a[rt].num = max(a[rt<<1].num,a[rt<<1|1].num);  
}  
int query(int lv,int rv,int rt)  
{  
    if(a[rt].l >= lv && rv >= a[rt].r)  
    {  
        return a[rt].num;  
    }  
    int ret = 0;  
    int m = (a[rt].l + a[rt].r) >> 1;  
    if(lv <= m)  
        ret = max(ret,query(lv,rv,rt<<1));  
    if(rv > m)  
        ret = max(ret,query(lv,rv,rt<<1|1));  
    return ret;  
}  
int main()  
{  
    int n,c,v;  
    int i,j,k,ma;  
    while(scanf("%d %d %d",&n,&c,&v)!=EOF)  
    {  
        build(1,v,1);  
        ma = 0;  
        for(i = 0;i < n; i++)  
            scanf("%d %d %d",&b[i].c,&b[i].v,&b[i].p);  
        sort(b,b+n,cmp);  
        for(i = 0,k = 0;i < n; i++)  
        {  
            if(i && b[i].c != b[i-1].c)  
            {  
                for(j = k; j < i; j++)  
                {  
                    update(b[j].v,b[j].p,1);  
                }  
                k = i;  
            }  
            int t = query(1,v - b[i].v,1);  
            if(t && b[i].p + t > ma)  
                ma = b[i].p + t;  
        }  
        if(ma)  
            printf("%d\n",ma);  
        else  
            puts("-1");           
    }  
    return 0;  
}  

 

 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,