[USACO17FEB]Why Did the Cow Cross the Road II P
2024-09-04 11:15:56
考虑dp。
对于ai,和他能匹配的bj只有9个,所以我们考虑从这9个状态转移。
对于ai 能匹配的一个bj,当前最大的匹配数一定是[1, j - 1]中的最大匹配数 + 1。然后用树状数组维护前缀匹配数最大值就行了。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define rg register
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-;
const int maxn = 1e5 + ;
inline ll read()
{
ll ans = ;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) {last = ch; ch = getchar();}
while(isdigit(ch)) {ans = ans * + ch - ''; ch = getchar();}
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < ) x = -x, putchar('-');
if(x >= ) write(x / );
putchar(x % + '');
} int n, a[maxn], pos[maxn];
int Max[maxn]; int c[maxn];
int lowbit(int x)
{
return x & -x;
}
void add(int pos, int x)
{
for(; pos <= n && c[pos] < x; pos += lowbit(pos)) c[pos] = x;
}
int query(int pos)
{
int ret = ;
for(; pos; pos -= lowbit(pos)) if(c[pos] > ret) ret = c[pos];
return ret;
} int main()
{
n = read();
for(int i = ; i <= n; ++i) a[i] = read();
for(int i = ; i <= n; ++i) {int x = read(); pos[x] = i;}
for(int i = ; i <= n; ++i)
{
for(int j = max(, a[i] - ); j <= min(n, a[i] + ); ++j)
Max[j] = query(pos[j] - );
for(int j = max(, a[i] - ); j <= min(n, a[i] + ); ++j)
add(pos[j], Max[j] + );
}
write(query(n)), enter;
return ;
}
最新文章
- iOS 之图片尺寸
- jQuery中的事件处理
- Cen0S下挂载设备
- 利用border-radious画图形
- java虚拟机运行时乱码问题
- 78 mount 挂载Linux系统外的文件。
- Unity手游之路<;四>;3d旋转-四元数,欧拉角和变幻矩阵
- Android 手机上安装并运行 Ubuntu 12.04(转,没实测)
- javascript中的__proto__和prototype
- (cvpr2019) The Degradation Model and Solution of DPSR
- socket网络编程-----I/O复用之poll函数
- 洛谷P4546 [THUWC2017]在美妙的数学王国中畅游 [LCT,泰勒展开]
- 最短路:spfa算法
- html 高亮显示表格当前行【转】
- HBase官方文档 之 Region的相关知识
- C#中利用LightningChart绘制曲线图表
- 使用PyInstaller打包Python角本为exe程序
- CREATESTRUCT cs 结构体
- 文件上传之 commons-fileupload(一)
- Cocos暂停和重新开始游戏