生活随笔
收集整理的這篇文章主要介紹了
HDU6638 Snowy Smile
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
http://acm.hdu.edu.cn/showproblem.php?pid=6638
題意：平面上有n個(gè)帶權(quán)點(diǎn)，問用一個(gè)矩形圍住的所有點(diǎn)權(quán)和最大是多少？
思路：把y坐標(biāo)離散化，然后按x排序，枚舉右邊界，依次一列一列地加點(diǎn)，依次求最大子段和。
復(fù)雜度O(n?nlog(n))O(n*nlog(n))O(n?nlog(n))
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=2010;
typedef long long ll
;int T
,n
;
struct Point
{int x
,y
,w
;bool operator < (Point z
){return x
>z
.x
;}
}p
[maxn
];ll lmax
[maxn
*4],rmax
[maxn
*4],maxx
[maxn
*4],sumv
[maxn
*4];void build()
{memset(lmax
,0,sizeof(lmax
));memset(rmax
,0,sizeof(rmax
));memset(maxx
,0,sizeof(maxx
));memset(sumv
,0,sizeof(sumv
));
}void maintain(int o
)
{int lc
=o
*2,rc
=o
*2+1;sumv
[o
]=sumv
[lc
]+sumv
[rc
];maxx
[o
]=max(maxx
[lc
],maxx
[rc
]);maxx
[o
]=max(maxx
[o
],rmax
[lc
]+lmax
[rc
]);lmax
[o
]=max(lmax
[lc
],sumv
[lc
]+lmax
[rc
]);rmax
[o
]=max(rmax
[rc
],sumv
[rc
]+rmax
[lc
]);
}void update(int o
,int l
,int r
,int p
,int v
)
{if(l
==r
){sumv
[o
]+=v
;lmax
[o
]+=v
;rmax
[o
]+=v
;maxx
[o
]+=v
;}else{int m
=(l
+r
)/2;if(p
<=m
)update(o
*2,l
,m
,p
,v
);else update(o
*2+1,m
+1,r
,p
,v
);maintain(o
);}
}int main()
{cin
>>T
;while(T
--){cin
>>n
;vector
<int> v
;for(int i
=1;i
<=n
;i
++){scanf("%d%d%d",&p
[i
].x
,&p
[i
].y
,&p
[i
].w
);v
.push_back(p
[i
].y
);}sort(v
.begin(),v
.end());v
.erase(unique(v
.begin(),v
.end()),v
.end());int sz
=v
.size();for(int i
=1;i
<=n
;i
++)p
[i
].y
=lower_bound(v
.begin(),v
.end(),p
[i
].y
)-v
.begin()+1;sort(p
+1,p
+1+n
);ll ans
=0; for(int i
=1;i
<=n
;i
++){if(i
!=1&&p
[i
].x
==p
[i
-1].x
)continue;build();int j
=i
,start
=i
;while(j
<=n
){while(j
<=n
){if(j
!=start
&& p
[j
].x
!=p
[j
-1].x
)break;update(1,1,n
,p
[j
].y
,p
[j
].w
);j
++;}ans
=max(ans
,maxx
[1]);start
=j
;}}cout
<<ans
<<endl
;}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的HDU6638 Snowy Smile的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
