HDU 6447 YJJ's Salesman(离散化+树状数组+dp)

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6447

       题意是有一个1e9*1e9的地图，有1e5个村庄，有一个人从(0,0)开始往(1e9,1e9)走，他每次只能向右、向下、向右下走一个单位，当他从一个地方向右下走到一个村庄时(从(x,y)走到(x+1,y+1)的时候)，他就可以获得这个村庄的权值，问他能获得的最大权值是多少。

       比赛的时候还是自己太菜了，除了搜索不知道还用啥方法，但是这么大的地图，搜索肯定是写不了(我当时还真的写了一个bfs)，过了这么多天才来补这道题(承认我比较懒)...

        首先看下题，这么大的地图只有1e5个村庄，所以我们可以把1e9*1e9的地图离散化成1e5*1e5的，然后我们用dp[i]来表示当走到第i个村庄所获得的最大价值，用树状数组去维护1到y-1区间的最大值然后加上当前村庄的权值就是到达这个村庄的最大值了。还是自己太菜...

下面是官方题解：

     

---

AC代码：

题目来源：2018中国大学生程序设计竞赛 - 网络选拔赛 1010

#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct Node{
  int x,y,val;
  bool operator < (const Node &a) const {     // 按x坐标排序
    if(a.x == x) return y < a.y;
    return x < a.x;
  }
  void input(){
    scanf("%d%d%d",&x,&y,&val);
  }
}Edge[maxn];
int pre[maxn],dp[maxn],a[maxn];
int T,n,num,ans,pos;

void init(){
  pos = 1;
  ans = 0;
  memset(pre,0,sizeof(pre));
  for(int i=1;i<=n;i++) dp[i] = Edge[i].val;
}

int lowbit(int x){return x & (-x);}

void Update(int x,int val){
  for(int i=x;i<=num;i+=lowbit(i)) pre[i] = max(pre[i], val);
}

int Query(int x){
  int ans = 0;
  for(int i=x;i>0;i-=lowbit(i)) ans = max(ans, pre[i]);
  return ans;
}

int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
      Edge[i].input();
      a[i] = Edge[i].y;
    }
    //-----------------------------------------------------------
    //                      离散化过程
    sort(a + 1, a + 1 + n);
    num = unique(a + 1, a + 1 + n) - a - 1;
    for(int i=1;i<=n;i++){
      Edge[i].y = lower_bound(a + 1, a + 1 + num, Edge[i].y) - a;
    }
    sort(Edge + 1, Edge + 1 + n);
    //-----------------------------------------------------------
    init();
    for(int i=1;i<=n;i++){      // 遍历
      while(Edge[pos].x < Edge[i].x){   // 更新1到pos行的最大值
        Update(Edge[pos].y, dp[pos]);
        pos ++;
      }
      dp[i] = Query(Edge[i].y - 1) + Edge[i].val;  // 更新第i个村庄获得的最大值
      ans = max(ans, dp[i]);
    }
    printf("%d\n",ans);
  }
  return 0;
}