nowcoder941B 弹钢琴
2019-08-16 07:43:59来源:博客园 阅读 ()
nowcoder941B 弹钢琴
题目链接
思路
首先按照音色排个序,顺便离散化一下音高。
用\(h[i]\)表示第\(i\)个键的音高,用\(w[i]\)表示第\(i\)个键的春希度。
朴素\(dp\)
\(f[i][j]\)表示前i个琴键,最高的音高为j时的最大收益。
那么当\(j\)大于\(h[i]\)时,就有\(f[i][j] = max(f[i-1][j],f[i-1][a[i]] + w[i])\)
否则就\(f[i][j] = f[i - 1][j]\)
优化
显然可以用树状数组优化(维护一个区间赋值和区间求最大值的操作)。
教训
发现了自己离散化的姿势是存在问题的!!
之前一直用\(map\)离散化,数据比较小了还体现不出来,数据比较大的时候就要比\(lower_bound\)慢很多。
对比
代码
/*
* @Author: wxyww
* @Date: 2019-06-28 19:59:57
* @Last Modified time: 2019-06-29 15:45:15
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
using namespace std;
typedef long long ll;
const int N = 1000000 + 100;
map<int,int>ma;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int ls[N];
struct node {
int x,y;int w;
}a[N];
int js;
ll tree[N];
void update(int pos,ll w) {
while(pos <= js) {
tree[pos] = max(tree[pos],w);
pos += pos & -pos;
}
}
ll query(int pos) {
ll ret = 0;
while(pos) {
ret = max(ret,tree[pos]);
pos -= pos & -pos;
}
return ret;
}
bool cmp(const node &A,const node &B) {
return A.x == B.x ? A.y < B.y : A.x < B.x;
}
int main() {
int n = read();
for(int i = 1;i <= n;++i) a[i].x = read() + 1,ls[i] = a[i].y = read() + 1,a[i].w = read();
sort(ls + 1,ls + n + 1);
sort(a + 1,a + n + 1,cmp);
js = n;
for(int i = 1;i <= n;++i)
a[i].y = lower_bound(ls + 1,ls + n + 1,a[i].y) - ls;
for(int i = 1;i <= n;++i) {
ll x = query(a[i].y) + a[i].w;
update(a[i].y,x);
}
cout<<query(js);
return 0;
}
原文链接:https://www.cnblogs.com/wxyww/p/nowcoder941B.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- NOI2010 超级钢琴 2018-06-27
- NOI2010 超级钢琴 2018-06-17
- [luogu2048] [bzoj2006] [NOI2010] 超级钢琴 题解 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash