BZOJ 4990 [USACO17FEB] Why Did the Cow Cross the Road II P (树状数组优化DP)
2024-08-29 02:08:05
题目大意:给你两个序列,你可以两个序列的点之间连边
要求:1.只能在点权差值不大于4的点之间连边
2.边和边不能相交
3.每个点只能连一次
设表示第一个序列进行到 i,第二个序列进行到 j,最多连的边数,容易得到方程:
不连边:
连边:
实际是这样的,每个位置如果想连边,就要从能连边的位置之前找最大值,即
直接转移不可取,由于最多只从9个位置转移,我们可以缩减一维,用记录b序列进行到位置 j 的最大连边数,再用树状数组维护的最大前缀和方便转移
#include <bits/stdc++.h>
#define N 200100
#define ll long long
using namespace std; int n,ans;
int a[N],b[N],hx[N],f[N],s[N];
void update(int x,int w) {for(int i=x;i<=n;i+=(i&(-i))) {s[i]=max(s[i],w);}}
int query(int x) {int ans=; for(int i=x;i>;i-=(i&(-i))) {ans=max(ans,s[i]);} return ans;} int main()
{
//freopen("Testdata.in","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) scanf("%d",&b[i]);
for(int i=;i<=n;i++) hx[b[i]]=i;
for(int i=;i<=n;i++)
{
for(int j=max(,a[i]-);j<=min(n,a[i]+);j++)
f[hx[j]]=query(hx[j]-);
for(int j=max(,a[i]-);j<=min(n,a[i]+);j++)
update(hx[j],f[hx[j]]+);
}
printf("%d\n",query(n));
return ;
}
最新文章
- UEditor百度富文本编辑器--让编辑器自适应宽度的解决方案
- UIBezierPath-绘制基本图形
- 老王讲自制RPC框架.(三.ZOOKEEPER)
- Javascript/jQuery 获取地址栏URL参数的方法
- 【vijos1900】 学姐吃寿司
- UISearchController Attempting to load the view of a view controller while it is deallocating is not allowed and may result in undefined behavior
- SQLAlchemy一对多总结
- Cmd命令
- 300.	Longest Increasing Subsequence
- #include <;QPushButton>;
- bresenham算法的FPGA的实现2
- Javascript DOM 02 在<;ul>;中创建、删除 <;li>;
- HTML5学习笔记<;三>;: HTML5样式, 连接和表格
- C语言第五次博客作业
- DragVideo,一种在播放视频时,可以任意拖拽的方案
- 解决linux root 认证失败的问题
- CSS3 - @keyframes
- shit vue &; shit iview
- html button 点击 显示倒计时秒数
- Android开发工程师文集-Fragment,适配器,轮播图,ScrollView,Gallery 图片浏览器,Android常用布局样式