DP训练——线段树优化DP
2020-02-25 本文已影响0人
云中翻月
线段树优化DP
HDU3698
题意
给定的矩阵
和
，须从
矩阵的每行选择一个数字，使得数字和最小。
选择时须保证前后选择的两个数字和
，满足
。
题解
状态定义：表示到第
行，当前行选第
列的最小花费。
边界：
目标：
转移方程：
目前的时间复杂度为。
我们考虑优化转移条件，将绝对值不等式打开，会发现
将k和j的关系在数轴上画出来，会发现。
因此，我们可以每行用一个线段树来维护这个区间上的最小值，通过懒惰标记进行区间修改和查询即可。
优化后的时间复杂度为。
代码如下
/*
*/
#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=100+5;
const int maxm=5000+5;
const int INF=0x3f3f3f3f;
int n,m,t[maxn][maxm],f[maxn][maxm];
int d[maxn][maxm];
struct SegmentTree{
int l,r,dat,tag;
}tr[maxm<<2];
int ans;
void init(){
ans=INF;
// memset(t,0,sizeof(t));
// memset(f,0,sizeof(f));
// memset(d,INF,sizeof(d));
}
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r){
tr[rt].dat=INF;
tr[rt].tag=INF; //INF表示没有标记
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
tr[rt].tag=min(tr[rt<<1].tag,tr[rt<<1|1].tag);
}
void spread(int rt){
if(tr[rt].tag!=INF){
tr[rt<<1].dat=min(tr[rt<<1].dat,tr[rt].tag);
tr[rt<<1|1].dat=min(tr[rt<<1|1].dat,tr[rt].tag);
tr[rt<<1].tag=min(tr[rt<<1].tag,tr[rt].tag);
tr[rt<<1|1].tag=min(tr[rt<<1|1].tag,tr[rt].tag);
tr[rt].tag=INF;
}
}
void update(int rt,int l,int r,int val){
if(tr[rt].l>=l&&tr[rt].r<=r){
tr[rt].dat=min(tr[rt].dat,val);
tr[rt].tag=min(tr[rt].tag,val);
return;
}
spread(rt);
int mid=tr[rt].l+tr[rt].r>>1;
if(l<=mid) update(rt<<1,l,r,val);
if(r>mid) update(rt<<1|1,l,r,val);
tr[rt].dat=min(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
int ask(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
spread(rt);
int mid=tr[rt].l+tr[rt].r>>1;
int res=INF;
if(l<=mid) res=min(res,ask(rt<<1,l,r));
if(r>mid) res=min(res,ask(rt<<1|1,l,r));
return res;
}
void dp(){
for(int i=1;i<=m;i++) d[1][i]=t[1][i];
for(int i=2;i<=n;i++){
build(1,1,m);
// for(int j=1;j<=m;j++) D(f[i-1][j]);
// E;
for(int j=1;j<=m;j++) update(1,j-f[i-1][j],j+f[i-1][j],d[i-1][j]);
for(int j=1;j<=m;j++){
int temp=ask(1,j-f[i][j],j+f[i][j]);
// D(temp);E;
d[i][j]=temp+t[i][j];
}
// for(int j=1;j<=m;j++) cout<<d[i][j]<<" ";
// E;
/*
9 5 3 8 7
8 2 6 8 9
1 9 7 8 6
0 1 0 1 2
1 0 2 1 1
0 2 1 0 2
*/
}
for(int i=1;i<=m;i++) ans=min(ans,d[n][i]);
printf("%d\n",ans);
}
int main() {
ios::sync_with_stdio(false);
// freopen("HDU3698.in","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
if(!n&&!m) break;
init();
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&t[i][j]);
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&f[i][j]);
/*
cout<<endl<<"-------"<<endl;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<t[i][j]<<" ";
}
cout<<endl;
}
cout<<endl<<"-------"<<endl;
*/
dp();
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
HDU4719
题意
个数排成一行，可以将其分为若干组，每组长度不大于给定常数
。
设第i组的最后一个数字为，则分组时需保证
，同时对应贡献为
。
求贡献和的最大值。
题解
首先考虑朴素dp。
状态定义：表示处理好前
个人，并且以
结尾的最大分数。
边界：,其他为
目标：
转移方程：
分离变量后，转移方程变化为
即需要用线段树，高效求解区间上
的最大值。
这时遇到一个问题，即如何保证区间上的
值都比
小。
这样相当于线段树有两个关键字和
，在满足第一关键字比
小的情况下，找一个
最大的。
这样其实是有一个套路的，既然反正只有第一关键字满足条件的能更新，那就干脆按照第一关键字排序。
其实，对于每个士兵，我们可以先按照身高来进行升序排列，如果身高相同，我们就按照编号（原来的顺序）降序排列，
然后对于排序后的士兵，我们设他原来的编号为
，则我们就查找线段树上
的价值，同时更新也是更新线段树上的
的位置。
因为对于每个士兵，如果在排序前能找到和他进行状态转移的士兵
，那么排序后，肯定有
。
还有一种更通俗的解释：
这题需要从小的开始处理，因为小的不受大的影响，所以先处理没关系。
但是如果遇到有相同的高度的点，
时，我们需要先处理排在后面的
。
因为如果先处理前面的，而且很不巧刚好j有最大值，那么处理i的时候就会查到那个值，但是这其实是非法的。
反之我们先处理后面的，此时
没有插入到线段树上，所以
不受影响。
而处理前面的j的时候，也是往左找，所以不受后面的i的影响，查询的时候只要保证查询区间长度不大与就行了。
代码如下
/*
*/
#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 ll INF=0x3f3f3f3f3f3f3f3fll;
int T;
int n,L;
struct node{
ll a;
int id;
bool operator<(const node& h)const{return a<h.a||(a==h.a&&id>h.id);}
}h[maxn];
struct SegmentTree{
int l,r;
ll dat;
}tr[maxn<<2];
ll f[maxn];
void init(){
memset(f,-1,sizeof(f));
}
void build(int rt,int l,int r){
tr[rt].l=l,tr[rt].r=r;
if(l==r){
tr[rt].dat=-INF;
return;
}
int mid=l+r>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
tr[rt].dat=max(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
void change(int rt,int x,ll v){
if(tr[rt].l==tr[rt].r){
tr[rt].dat=v;
return;
}
int mid=tr[rt].l+tr[rt].r>>1;
if(mid>=x) change(rt<<1,x,v);
if(mid<x) change(rt<<1|1,x,v);
tr[rt].dat=max(tr[rt<<1].dat,tr[rt<<1|1].dat);
}
ll query(int rt,int l,int r){
if(tr[rt].l>=l&&tr[rt].r<=r) return tr[rt].dat;
int mid=tr[rt].l+tr[rt].r>>1;
ll res=-INF;
if(mid>=l) res=max(res,query(rt<<1,l,r));
if(mid<r) res=max(res,query(rt<<1|1,l,r));
return res;
}
int main() {
// ios::sync_with_stdio(false);
//freopen("HDU4719.in","r",stdin);
scanf("%d",&T);
for(int kase=1;kase<=T;kase++){
init();
printf("Case #%d: ",kase);
scanf("%d%d",&n,&L);
for(int i=1;i<=n;i++){
scanf("%lld",&h[i].a);
h[i].id=i;
}
sort(h+1,h+n+1);
build(1,0,n);
change(1,0,0);
for(int i=1;i<=n;i++){
ll res=query(1,max(0,h[i].id-L),h[i].id-1);
if(res<0) continue;
f[h[i].id]=res+h[i].a*h[i].a;
change(1,h[i].id,f[h[i].id]-h[i].a);
}
if(~f[n]) printf("%lld\n",f[n]);
else printf("No solution\n");
}
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
