【题意】

顺序经过k个点,求获得的最大权值和。

【思路】

设f[i]表示到第i个点,则有转移式:

f[i]=min{ f[j]+w[i] } x[j]<=x[i],y[j]<=y[i]

满足的条件是一个二维偏序,可以将x排序后用BIT维护y区间上的最大值。

又因为y比较大,所以需要提前离散化y坐标。

【代码】

 #include<set>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long ll;
const int N = 5e5+; ll read() {
char c=getchar();
ll f=,x=;
while(!isdigit(c)) {
if(c=='-') f=-; c=getchar();
}
while(isdigit(c))
x=x*+c-'',c=getchar();
return x*f;
} ll C[N],tot;
void upd(int x,ll v)
{
for(;x<=tot;x+=x&-x)
C[x]=max(C[x],v);
}
ll query(int x)
{
ll res=;
for(;x;x-=x&-x)
res=max(res,C[x]);
return res;
} struct Node {
int x,y,z;
bool operator < (const Node& rhs) const{
return x<rhs.x||(x==rhs.x&&y<rhs.y);
}
}ns[N]; int r,c,n;
int hash[N*]; int main()
{
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
r=read(),c=read(),n=read();
FOR(i,,n) {
ns[i].x=read(),ns[i].y=read(),ns[i].z=read();
hash[++tot]=ns[i].x,hash[++tot]=ns[i].y;
}
sort(hash+,hash+tot+);
tot=unique(hash+,hash+tot+)-hash-;
FOR(i,,n)
ns[i].y=lower_bound(hash+,hash+tot+,ns[i].y)-hash;
sort(ns+,ns+n+);
ll ans=;
FOR(i,,n) {
ll x=query(ns[i].y)+ns[i].z;
ans=max(ans,x);
upd(ns[i].y,x);
}
printf("%d",ans);
return ;
}

最新文章

  1. Oracle REGEXP_SUBSTR()
  2. CSS之伪类
  3. Jekyll教程——精心收藏
  4. 第 12 章 CSS 入门
  5. P1072 Hankson 的趣味题
  6. MySQL学习笔记01-MYSQL安装
  7. Unity 3D 关于给APK包加广告的流程
  8. linux上操作mysql数据库
  9. 《App研发录》知识点汇总
  10. Chrome developer tool:本人钟爱的 console、Network 功能简谈
  11. whu oj 1551 Pairs (莫队算法)
  12. Linux CentOS 安装 httpd
  13. KVM 时钟分析
  14. DS博客作业01—日期抽象数据类型设计与实现
  15. connector for python实验
  16. win10企业版永久激活方法
  17. mactype配置
  18. CSS单位【记录】
  19. WPF 显示 mp3 专辑图片
  20. Web版微信协议分析—版本2

热门文章

  1. Android:Android SDK Manager顺利下载
  2. WCF入门(二)-----实战开发
  3. [cocoapods] 如何卸载工程里的cocoapods
  4. ubuntu下安装Ming的教程
  5. Collection_Other
  6. Xcode学习
  7. HDU 4565 So Easy!(矩阵)
  8. [NYIST16]矩形嵌套(DP,最长上升子序列)
  9. 给你的JAVA程序配置参数(Properties的使用)
  10. bzoj1043