DP学习

DP入门学习

清华大学翁家翌将其分为 $8$ 类，分别为序列DP、区间DP、坐标DP、数轴DP、树型DP、数位DP、状压DP、记忆化搜索。

北京大学yxc将其分为 $10$ 类，分别为背包问题、线性DP、区间DP、计数DP、数位DP、状压DP、树形DP、记忆化搜索、基环树DP、插头DP。

罗勇军老师的《算法竞赛》和洛谷进阶篇将其分为 $4$ 类，分别为数位DP、状压DP、区间DP、树形DP。

除了上述状态类型外，还有优化。

优化基本有单调队列优化、斜率优化、四边形不等式优化。

D. Serval and Kaitenzushi Buffet

xglixzk提供的题目

https://codeforces.com/contest/2085/problem/D

取 \(i\) 盘寿司的时间应该不晚于 \((n-i*(k+1)+1)\) 分钟，这个约束限制了可以取寿司的时间。

因此我们会按时间顺序列举 \(n\) 分钟，并在达到一个约束条件时，即当前分钟是某 \(i\) 的 \((n-i*(k+1)+1)\) 分钟时，贪心拿走之前美味值最大的盘子。

没取盘子的美味都可以通过 堆 来维护。总复杂度为 \(O(nlog n)\) 。

ll ans=0,n,k;
cin>>n>>k;
priority_queue<ll> q;
for(int i=1;i<=n;i++){
    int x;cin>>x;
    q.push(x);
    if((n-i+1)%(k+1)==0){
        ans+=q.top();
        q.pop();
    }
}
cout<<ans<<"\n";