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++ ,