HDU 6447 YJJ's Salesman (dp+树状数组+莫干山算法)
程序员文章站
2022-06-09 17:42:21
...
题意:一个 1e9*1e9的方格,从(0,0)走到(1e9,1e9),有个方格有价值,特殊的经过方格可获得价值,每次只能向右、下、右下走,只有右下走到方格的才能获得价值,问最大获得的价值是多少
官方题解:莫干山算法(逃
个人理解:
先把各个村庄离散化,然后按照从上到下,从右到左的顺序排序,以上下为主,左右为次,之后我们更新这个 f [ j ] ,由于每一列的最大值只能由上一行影响,所以更新的顺序应该是从上到下,从左向右,类似01背包的优化。我们遍历的时候直接从第一个村庄遍历到最后一个村庄,由于已经排好序,所以在遍历的过程中可实现自动换行遍历,用数状数组取得f [ j - 1 ]的值,更新f [ j ]。
ps:后来发现不离散化这题也能过,数据出了问题。
代码:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <iomanip>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define mod 1000000007
#define lowbit(x) (x&(-x))
#define mem(a,b) memset(a,b,sizeof(a))
#define FRER() freopen("in.txt","r",stdin);
#define FREW() freopen("out.txt","w",stdout);
using namespace std;
typedef pair<int,int> pii;
const int maxn = 100000 + 7, inf = 0x3f3f3f3f ;
struct Node{
int x,y,v;
bool operator < (const Node& rhs) const {
return x == rhs.x ? y > rhs.y : x < rhs.x;
}
}nodes[maxn];
int c[maxn];
void add(int x,int val){
while(x < maxn){
c[x] = max(c[x],val);
x += lowbit(x);
}
}
int query(int x){
int res = 0;
while(x){
res = max(res,c[x]);
x -= lowbit(x);
}
return res;
}
void Init(){
mem(c,0),mem(nodes,0);
}
int main() {
//FRER();
//FREW();
int T;
scanf("%d",&T);
while(T--){
Init();
int n;
scanf("%d",&n);
int cnt1 = 0 , cnt2 = 0;
for(int i=1;i<=n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
nodes[cnt2++] = {a,b,c};
}
sort(nodes,nodes+n);
for(int i=0;i<n;i++){
int val = query(nodes[i].y-1);
add(nodes[i].y,val+nodes[i].v);
}
int res = query(n);
cout<<res<<endl;
}
return 0;
}