树状数组DP
BZOJ1264
题意
给出两个长度均为的数字序列，求
。
数据保证每个序列中，到
共
个数字每个必然出现
次。
题解
题目说了一个数会出现次，那么我们可以预处理得到：第一个序列
每个数字分别在哪些位置。
因为求LCS的状态转移方程中当 时，
即只有当两个点相同时，值才会。
于是，我们可以对第二个序列遍历一遍，对于
我们可以找到它在
上的
个位置，这
个位置的
都可以被更新。
更新时用树状数组维护dp数组即可。
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=20000*5+5;
const int INF=0x3f3f3f3f;
int n;
int a[maxn],b[maxn];
int c[maxn];
vector<int>p[maxn/5];
int f[maxn]; //f[i]表示以a[i]结尾的与b序列的最长LCS长度
int ans=0;
void add(int x,int v){
for(int i=x;i<=n;i+=i&-i) c[i]=max(c[i],v);
}
int query(int x){
int res=0;
for(int i=x;i>=1;i-=i&-i) res=max(res,c[i]);
return res;
}
void dp(){
for(int i=1;i<=n;i++){
for(int j=p[b[i]].size()-1;j>=0;j--){
int pos=p[b[i]][j];
f[pos]=query(pos-1)+1;
// D(pos);D(f[pos]);E;
add(pos,f[pos]);
}
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
}
int main() {
ios::sync_with_stdio(false);
//freopen("BZOJ1264.in","r",stdin);
scanf("%d",&n);
n*=5;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
p[a[i]].push_back(i); //记录每个数字的位置
}
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
dp();
printf("%d",ans);
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
BZOJ3594
题意
个数字排成一行，最多进行
次操作。
每次可以将一个区间内所有数字，或者去除任意个数字。
为使得最后的序列单调不下降，求最后剩余的数字个数的最大值。
题解
状态定义：表示以
结尾，被
个拔高区间覆盖过的最长单调不下降子序列的长度
目标：
边界：
转移方程：
时间复杂度
考虑优化时间复杂度。
正常的二维树状数组只可以维护中的两个条件，又注意到第一维可以用类似
背包的思想压缩。
因此将状态第一维压缩，将这个条件转化到状态定义中，再将第三维的枚举改为逆序循环（避免第一维均为
的状态间相互转移），即可用二维树状数组维护
数组的最值。
状态定义：表示以
结尾，高度（拔高后的高度）小于等于
，被
个拔高区间覆盖过的最长单调不下降子序列的长度
目标：
边界：
转移方程：
PS：
拔高次数范围为，树状数组不能处理
这个下标，所以这里将范围转化为
。
因为数组为中间量，所以并没有在代码中显式定义。
题解链接 https://www.luogu.com.cn/problemnew/solution/P3287
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=10000+5;
const int maxa=5000+5;
const int maxk=500+5;
const int INF=0x3f3f3f3f;
int n,k;
int a[maxn];
int c[maxa+maxk][maxk];
int mx1=-INF,mx2;
int ans=-INF;
void add(int x,int y,int v){
for(int i=x;i<=mx1;i+=i&-i) for(int j=y;j<=mx2;j+=j&-j) c[i][j]=max(c[i][j],v);
}
int ask(int x,int y){
int res=-INF;
for(int i=x;i>=1;i-=i&-i) for(int j=y;j>=1;j-=j&-j) res=max(res,c[i][j]);
return res;
}
void dp(){
/*
f[i,j,k]表示当前这个点i是（从左往右枚举点），
以一个高度（拔高后的高度）小于等于j(j=h[i]+k)，
被小于等于k个拔高区间覆盖过的点为结尾的最长不下降序列的长度。
利用类似于01背包的特性，可以去掉状态的第一维，但k的循环要变成逆序。（状态中的j可以通过i和k算出）
c[i,j]表示以高度小于等于i，被拔高区间的覆盖次数小于等于j的点为结尾的所有不下降序列长度的最大值
*/
for(int i=1;i<=n;i++){
for(int j=k;j>=0;j--){
int temp=ask(a[i]+j,j+1)+1; //j+1的原因是树状数组不能处理0这个下标，所以这一维上的下标需要向右平移一个单位
ans=max(ans,temp);
add(a[i]+j,j+1,temp);
}
}
}
int main() {
// ios::sync_with_stdio(false);
//freopen("BZOJ3594.in","r",stdin);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
mx1=max(mx1,a[i]);
}
mx1+=k; //最大玉米高度为max{a[i]}+k
mx2=k+1; //拔高次数范围为[0,k]，树状数组不能处理0这个下标，所以这里将范围转化为[1,k+1]
dp();
printf("%d",ans);
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
BZOJ2131
题意
个馅饼，第
个馅饼分值为
在
时刻，落在
位置，
处于
坐标范围内。
玩家初始时刻可处于任意位置，每个时刻可以向左右移动不超过两格，求接到的馅饼分值和的最大值。
题解
首先考虑朴素dp，将馅饼按照落地时间排序。
状态定义：表示接住第
个馅饼的最大分值
目标：
边界：
转移方程：
时间复杂度
考虑优化时间复杂度。
注意到转移时需要维护满足的最大
，故尝试拆解该条件。
去绝对之后，该条件转换为
分离参数得
令得
即将条件转化为维护二维前驱最大值，使用二维树状数组维护即可。
PS：为了解决二维树状数组空间过大的问题，可对数组进行排序后，离散化
数组。
题解链接 https://blog.csdn.net/jaihk662/article/details/78145476
代码如下
/*
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
int W,n;
struct node{
int x,y,v;
bool operator<(const node& h)const{return y<h.y||(y==h.y&&x<h.x);}
}pie[maxn];
int f[maxn];
int c[maxn];
int a[maxn],cnt=0;
void add(int x,int v){
for(int i=x;i<=cnt;i+=i&-i) c[i]=max(c[i],v);
}
int ask(int x){
int res=-INF;
for(int i=x;i>=1;i-=i&-i) res=max(res,c[i]);
return res;
}
void pre(){
sort(pie+1,pie+n+1);
sort(a+1,a+cnt+1);
cnt=unique(a+1,a+cnt+1)-a-1;
}
void dp(){
for(int i=1;i<=n;i++){ //循环顺序保证了y递增
int pos=lower_bound(a+1,a+cnt+1,pie[i].x)-a; //二分查找后 得到符合条件的x下标
f[pos]=ask(pos)+pie[i].v;
add(pos,f[pos]);
}
}
int main() {
ios::sync_with_stdio(false);
//freopen("BZOJ2131.in","r",stdin);
scanf("%d%d",&W,&n);
int t,p;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&t,&p,&pie[i].v);
pie[i].x=2*t+p;
pie[i].y=2*t-p;
a[++cnt]=pie[i].x;
}
pre();
dp();
printf("%d",ask(cnt)); //注意这里不是f[cnt]，因为此时的f[cnt]里存储值时没有加入最后一块馅饼的状态
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
网友评论