欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 6447 YJJ's Salesman (dp+树状数组+莫干山算法)

程序员文章站 2022-06-09 17:42:21
...

题意:一个 1e9*1e9的方格,从(0,0)走到(1e9,1e9),有个方格有价值,特殊的经过方格可获得价值,每次只能向右、下、右下走,只有右下走到方格的才能获得价值,问最大获得的价值是多少

官方题解:莫干山算法(逃

HDU 6447 YJJ's Salesman (dp+树状数组+莫干山算法)

个人理解:

先把各个村庄离散化,然后按照从上到下,从右到左的顺序排序,以上下为主,左右为次,之后我们更新这个 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;
}