#507. 「LibreOJ NOI Round #1」接竹竿 dp
2024-09-01 19:22:22
题目:
题解:
我们考虑把每对花色相同的牌看作区间。
那么如果我们设 \(f_i\) 表示决策在 \([1,i]\) 内的最优答案.
那么有 \(f_i = max\{max\{(f_{j-1}+\sum_{k=j}^iv_k) | a_{j-1} = a_i\},f_{i-1}\}\)
我们可以记录每个点上一次出现的位置 \(la_i\).
那么每次我们更新的时候用 \(la\) 跳转即可。
然后我们发现每个数只能用和它相同的数的位置转移过来。
所以实际上这分成了若干的转移线。
然后我们发现在每条转移线上的转移点是单调的。
并且转移点更新的条件是用下一个地方转移比得到的区间价值和更大。
所以可以做到 \(O(n)\)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;static char ch;static bool flag;flag =false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
#define rg register int
#define rep(i,a,b) for(rg i=(a);i<=(b);++i)
#define per(i,a,b) for(rg i=(a);i>=(b);--i)
const int maxn = 1000010;
int c[maxn],v[maxn],ws[maxn],la[maxn];
ll s[maxn],f[maxn];int g[maxn];
int main(){
int n,m;read(n);read(m);
rep(i,1,n) read(c[i]);
rep(i,1,n) read(v[i]),s[i] = s[i-1] + v[i];
rep(i,1,n){
g[c[i]] = 0;
la[i] = ws[c[i]];
ws[c[i]] = i;
}
f[0] = 0;
rep(i,1,n){
f[i] = f[i-1];
if(la[i] != 0){
f[i] = max(f[i],f[g[c[i]]-1]+s[i]-s[g[c[i]]-1]);
if(f[i-1] - f[g[c[i]]-1] > s[i-1] - s[g[c[i]]-1]) g[c[i]] = i;
}else g[c[i]] = i;
}printf("%lld\n",f[n]);
return 0;
}
最新文章
- .cn根服务器被攻击之后
- AppleWatch___学习笔记(三)iPhone和Apple Watch上的数据同步
- 改造一下C# Substring()函数
- HighCharts基本使用实例(入门)
- deep learning 学习资料
- python3-day4(re正则表达式,冒泡)
- AngularJs练习Demo11引入Jquery
- log4cplus配置文件使用
- document.write()相关
- java 类 及其 执行过程
- jQuery插件实现左右无缝轮播
- Excel教程(4) - 数据库函数
- zend framework 1.10项目配置与经典hello world
- windown快速安装xgboost
- 导弹拦截(pascal)
- Linux Debugging(三): C++函数调用的参数传递方法总结(通过gdb+反汇编)
- Python学习过程中各个难点---数据类型篇
- Bash Shebang 小结
- VS2013中Python学习笔记[环境搭建]
- DLL.LoadLibrary失败(126)