3 条题解
-
3
其实可以用优先队列,只是多带个 log 而已code:
#include<bits/stdc++.h> using namespace std; #define int long long const int N=1e6+5; int n,h[N],w[N],k,d; struct node{ int sum,h,id; }; bool operator < (node a,node b){ if(a.sum!=b.sum) return a.sum>b.sum; return a.h<b.h; } node makenode(int x,int y,int z){ node aa; aa.sum=x; aa.h=y; aa.id=z; return aa; } priority_queue<node> pq; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>d; for(int i=1;i<=n;i++) cin>>h[i]>>w[i]; pq.push(makenode(w[1],h[1],1)); for(int i=2;i<=n;i++){ node y=pq.top(); while(i-y.id>k){ pq.pop(); y=pq.top(); } if(h[i]>h[y.id]) pq.push(makenode(y.sum+w[i]+d,h[i],i)); else pq.push(makenode(y.sum+w[i],h[i],i)); } node y=pq.top(); while(y.id!=n){ pq.pop(); y=pq.top(); } cout<<y.sum; return 0; } -
0
啧,我承认当我写了半小时快写完的题解结果不小心刷新掉的时候我是绝望的
重写一遍吧
正文: 60pts(理论上的但实际上因为数据水可以过): n^2^的20加上d=0单调队列板子的40 代码如下:
#include<bits/stdc++.h> using namespace std; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n,k,d; long long f[300005]; struct node{ int h,w; }a[300005]; int lhh(int x,int y){ if(a[x].h>=a[y].h)return d; else return 0; } void syn(){//单调队列板子优化 deque<int> q; q.push_back(1); for(int i=2;i<=n;i++){ while(!q.empty()&&q.front()<i-k){ q.pop_front(); } f[i]=min(f[i],f[q.front()]+a[i].w); while(!q.empty()&&f[q.back()]>=f[i])q.pop_back(); q.push_back(i); } cout<<f[n]; } int main(){ lhhsyn(); cin>>n>>k>>d; for(int i=1;i<=n;i++){ cin>>a[i].h>>a[i].w; } for(int i=1;i<=n;i++){ f[i]=1e9; } f[1]=a[1].w; if(d==0){ syn(); return 0; } for(int i=2;i<=n;i++){ for(int j=1;j<=min(k,i-1);j++){ f[i]=min(f[i],f[i-j]+a[i].w+lhh(i,i-j)); } } cout<<f[n]; return 0; }那接下来是100分解。 其实也很好理解,就是相较板子多考虑了个状态h,因为考虑到d=1,所以比一个值体力值大的一定不可能创造比他还大的价值(因为最多加一)所以可以不管。但如果相等就不太一样,留下(选择)高度更高的那个,因为他更不容易+1,然后就还是板子了
代码如下:
#include<bits/stdc++.h> using namespace std; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n,k,d; long long f[300005]; struct node{ int h,w; }a[300005]; int lhh(int x,int y){ if(a[x].h>=a[y].h)return d; else return 0; } void syn(){ deque<int> q; q.push_back(1); for(int i=2;i<=n;i++){ while(!q.empty()&&q.front()<i-k){ q.pop_front(); } f[i]=min(f[i],f[q.front()]+a[i].w); while(!q.empty()&&f[q.back()]>=f[i])q.pop_back(); q.push_back(i); } cout<<f[n]; } deque<int> q1; int main(){ lhhsyn(); cin>>n>>k>>d; for(int i=1;i<=n;i++){ cin>>a[i].h>>a[i].w; } for(int i=1;i<=n;i++){ f[i]=1e9; } f[1]=a[1].w; if(d==0){ syn();//其实这个可以不要了但是对我的话选择不删 return 0; } q1.push_back(1); for(int i=2;i<=n;i++){ while(!q1.empty()&&q1.front()<i-k){ q1.pop_front(); } f[i]=min(f[i],f[q1.front()]+a[i].w+((a[i].h>=a[q1.front()].h)?d:0));//一个小改动 while(!q1.empty()&&f[q1.back()]>f[i])q1.pop_back();//还有这个地方要小于,小于等于的话下面那行没用了 while(!q1.empty()&&f[q1.back()]==f[i]&&a[q1.back()].h<=a[i].h)q1.pop_back();//唯一添加 q1.push_back(i); } cout<<f[n]; return 0; }我觉得我无论是题解还是代码写的比lzm的要优质有没有懂的依旧你OJ模拟赛神秘数据,n^2^就能过了。
话说我好歹还写了单调队列板子呢,lzm为什么对我意见那么大捏最后观看这篇题解的您要是觉得对您有帮助请麻烦点个赞呗(´・ω・`) -
0
单调队列 板子,无需多言。
不过不要忘记 ,否则 →。
另外,建议加强数据,使 等人的 做法仅获得 分。(不然这题不就成了下位橙了)
(
最好10分也别给。)#include <bits/stdc++.h> using namespace std; const int N = 3e5 + 5; int n, k, d, h[N], w[N], f[N]; struct node { int hh, fv, id; }; deque<node> q; int solve() { f[1] = w[1], q.push_back({h[1], f[1], 1}); for(int i=2; i<=k; ++i) { node np = q.front(); f[i] = np.fv + w[i] + (np.hh <= h[i]) * d; while(q.back().fv > f[i] && q.size()) q.pop_back(); while(q.back().fv == f[i] && q.back().hh < h[i] && q.size()) q.pop_back(); q.push_back({h[i], f[i], i}); } for(int i=k+1; i<=n; ++i) { while(q.front().id < i - k && q.size()) q.pop_front(); node np = q.front(); f[i] = np.fv + w[i] + (np.hh <= h[i]) * d; while(q.back().fv > f[i] && q.size()) q.pop_back(); while(q.back().fv == f[i] && q.back().hh < h[i] && q.size()) q.pop_back(); q.push_back({h[i], f[i], i}); } while(!q.empty()) q.pop_front(); return f[n]; } int main() { scanf("%d%d%d", &n, &k, &d); for(int i=1; i<=n; ++i) { scanf("%d%d", &h[i], &w[i]); } printf("%d\n", solve()); return 0; }
- 1
信息
- ID
- 929
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 52
- 已通过
- 18
- 上传者