花店橱窗布置
题目大意
在保持顺序的情况下,求摆放的最大美学值
做法
正常做法来说是dp,设dp[i][j]表示第i束花放不放在第j个花盆里的最大值,转移方程就应该是:
不放:$$dp[i][j]=dp[i][j-1]$$
放:$$dp[i][j]=dp[i-1][j-1]+a[i]$$
但是当时突发奇想,想了个线段树,没想到写过了,故来记录线段树做法,那么为什么可以用线段树做呢,可以发现, 下一层更新答案要在上一层的基础上再往下更新,第i束花最前可以放在第i个花盆(题意),那么\(f[i][j]\)表示第i束花放在第j个花盆的最大值,那么他一定是由\(max(f[i-1][i-1...j-1])\)更新来的,看到这个方程第一眼想到了单调队列去维护,但发现这个长度不是固定的,所以不能用这个来维护,那么还能动态维护区间最大值的方式就想到了线段树。把原来线段树维护的\(sum\)改成维护\(max\)可行,因为每一层都只跟上一层有关,所以线段树只需要维护上一层的信息就可以,而又因为\(f[i][]\)只跟\(f[i-1][]\)有关,故线段树相当于那个压成一维的滚动数组,更新就要倒着更新。\(dp是O(nm)的复杂度,线段树维护只多了一个log(m),故是O(nmlogm)的复杂度,可以过全部数据\)
洛谷P1854
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 105,inf = 2147483647;
int n,m,f[maxn][maxn],a[maxn][maxn],res,pos,pre[maxn][maxn],ans[maxn];
struct Tree{
int l,r,k,maxi,pos;
}tree[maxn<<2];
void build(int l,int r,int k)
{
tree[k] = (Tree){l,r,k,0};
if(l == r)
{
tree[k].maxi = a[1][l];
tree[k].pos = l;
return ;
}
int mid = l + r >> 1;
build(l,mid,k<<1);
build(mid+1,r,(k<<1)+1);
if(tree[k<<1].maxi >= tree[(k<<1)+1].maxi)
{
tree[k].maxi = tree[k<<1].maxi;
tree[k].pos = tree[k<<1].pos;
}
else{
tree[k].maxi = tree[(k<<1)+1].maxi;
tree[k].pos = tree[(k<<1)+1].pos;
}
return ;
}
void update(int p,int v,int k)
{
if(tree[k].l == tree[k].r)
{
tree[k].maxi = v;
return ;
}
int mid = tree[k].l + tree[k].r >> 1;
if(p <= mid)
update(p,v,k<<1);
else update(p,v,(k<<1)+1);
if(tree[k<<1].maxi >= tree[(k<<1)+1].maxi)
{
tree[k].maxi = tree[k<<1].maxi;
tree[k].pos = tree[k<<1].pos;
}
else{
tree[k].maxi = tree[(k<<1)+1].maxi;
tree[k].pos = tree[(k<<1)+1].pos;
}
return ;
}
void query(int l,int r,int k)
{
if(tree[k].l >= l && tree[k].r <= r)
{
if(tree[k].maxi >= res)
{
res = tree[k].maxi;
pos = tree[k].pos;
}
return ;
}
int mid = (tree[k].l + tree[k].r) >> 1;
if(l <= mid)
query(l,r,k<<1);
if(r > mid)
query(l,r,(k<<1)+1);
return ;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
build(1,m,1);
for(int i=2;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
if(j >= i)//最前要在第i位
{
res = -inf;
query(i-1,j-1,1);//查询i-1到j-1的最大值
f[i][j] = res + a[i][j];//更新答案
pre[i][j] = pos;//记录f[i][j]是由上一层的哪个更新而来
update(j,f[i][j],1);//同时修改线段树中的值
}
else update(j,-inf,1);//前面的更新为负无穷,这样不会影响答案
}
}
printf("%d\n",tree[1].maxi);//最终答案肯定是f[n][n...m]中的最大值,
int k = n,mpos = tree[1].pos,cnt = 0;
ans[++cnt] = mpos;
while(pre[k][mpos])
{
ans[++cnt] = pre[k][mpos];
mpos = pre[k][mpos];
k --;
}
for(int i=cnt;i>=1;i--)
printf("%d ",ans[i]);
return 0;
}
标签:花店,橱窗,mpos,线段,tree,pos,maxn,dp,布置
From: https://www.cnblogs.com/-Wind-/p/18127951