递增子序列

题意：给定n个数，问长度为m的递增子序列数量

构造dp数组

dp[i][j]表示以第i个元素结尾的长度为j的上升子序列个数

构造转移方程

dp[i][j]=∑a[k]<a[i]&&k<i (dp[k][j-1])

考虑朴素做法

显然只需枚举i，j，k即可完成本题

但显然时间复杂度O(n^2m) 不能接受

考虑数据结构优化DP

不难发现，转移方程实际上对a数组进行了顺序对求和，由顺序对容易想到树状数组，所以考虑使用树状数组省去对k的枚举使时间复杂度降低至O(nmlogn)发现可以通过此题，遂实施

具体实施

#include<bits/stdc++.h>
using namespace std;

#define ll long long 
#define mod 123456789

const int MAXN=10010;
const int MAXM=105;

int n,m;
struct Array //数组 但是原地离散化
{
    ll initvalue;
    int id;
    int lsvalue;
}a[MAXN];
bool cmpinitvalue(Array x,Array y) 
{
    return (x.initvalue<y.initvalue);
}
bool cmpid(Array x,Array y) 
{
    return (x.id<y.id);
}

struct BinaryIndexTree //把BIT封装起来
{
    ll b[MAXN];
    void clear()
    {
        memset(b,0,sizeof(b));
    }
    int lowbit(int k)
    {
        return k&(-k);
    }
    void Modify(int k,ll v)
    {
        for(int i=k;i<=10000;i+=((-i)&(i))) b[i]=(b[i]+v)%mod;
        return ;
    }
    ll Query(int k)
    {
        ll ans=0;
        while(k>0)
        {
            ans+=b[k];
            ans%=mod;
            k-=lowbit(k);
        }
        return ans%mod;
    }
}Bit[MAXM];//开M个BIT，相比书上更好理解

void init()//离散化
{
    for(int j=1;j<=m;j++) Bit[j].clear();
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i].initvalue);
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmpinitvalue);
    int idx=0;
    a[0].initvalue=-1;
    for(int i=1;i<=n;i++) 
    {
        if(a[i].initvalue==a[i-1].initvalue) a[i].lsvalue=idx;
        else a[i].lsvalue=++idx;
    }
    sort(a+1,a+1+n,cmpid);
}

void work()//区间求和
{
    for(int i=1;i<=n;i++)
    {
        Bit[1].Modify(a[i].lsvalue,1);
        for(int j=2;j<=m;j++)
        {
            ll temp=Bit[j-1].Query(a[i].lsvalue-1);
            if(!temp) break;
            Bit[j].Modify(a[i].lsvalue,temp%mod);
        }
    }   
    cout<<Bit[m].Query(n)%mod;
}

int main()
{
    // freopen("working.in","r",stdin);
    // freopen("working.out","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        work();
        cout<<endl;
    }
    return 0;
}

基站选址

题意：给定n个在直线上的村庄，需要建立不超过k个基站

在第i个村庄建立基站费用为Ci

如果第i个村庄不超过Si的距离内有基站，这个村庄被覆盖了

如果第i个村庄没有被覆盖，则需要补偿这个村庄Wi费用

构造dp数组

f[i][j]=min(f[k][j-1]+pay[k][i])

其中设f[i][j]表示在前i个村庄内，第j个基站建在i处的最小费用（不考虑i~n的赔偿费用）

pay[k][i]表示第k个村庄到第i个村庄的赔偿费用之和

考虑朴素做法

空间复杂度O(n^2)

时间复杂度O(kn^2)

不可接受

优化空间

那么我们观察上面这个方程，可以发现类似于背包问题，可以直接滚掉一维。改造方程:

f[i]=min(f[k]+pay[k][i])

优化时间

主要的时间消耗在了哪里？自然是怎么快速计算pay[k][i]了

那么我们思考：

对于每一个村庄，都有一个范围内需要建立基站，否则就要赔偿，那么我们设第i个村庄的范围为[L,R],如果正在考虑R处建不建基站，那么有下列情况：

1、不在R处设立基站，那么对于村庄i来说，上一个基站在[1,L−1]这个区间的话，就要赔偿村庄i了，因为[L,R]这个区间没有建基站，那么我们就要快速的在[1,L−1]中区间加村庄i的赔偿费用了，我们就以线段树为例啦

2、在R处建立基站，那么也就相当于最后一个基站设立在[1,R−1]这个区间中，找一个费用最小值来转移嘛，还是线段树

所以我们要开一个线段树来维护f+pay的最小值，要有区间加法和区间查询的操作

st[i]表示第i个村庄对应区间的左端点L

ed[i]表示第i个村庄对应区间的右端点R

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20007
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
struct Edge
{
	int to,nxt;
}edge[N<<2];
struct Tree
{
	int date,mark;
}tr[N<<2];
int n,k,cnt;
int dis[N],val[N],range[N],pay[N],st[N],ed[N],head[N],f[N];
void Add(int u,int v)
{
	edge[++cnt]=(Edge){v,head[u]};
	head[u]=cnt;
}
void Get()
{
	for(int i=1;i<=n;++i)
	{
		st[i]=lower_bound(dis+1,dis+1+n,dis[i]-range[i])-dis;
		ed[i]=lower_bound(dis+1,dis+1+n,dis[i]+range[i])-dis;
		if(dis[ed[i]]>dis[i]+range[i])
			--ed[i];
		Add(ed[i],i);
	}
}
void Pushup(int rt)
{
	tr[rt].date=min(tr[rt<<1].date,tr[rt<<1|1].date);
}
void Build(int rt,int l,int r)
{
	tr[rt].mark=0;
	if(l==r)
	{
		tr[rt].date=f[l];
		return;
	}
	int mid=l+((r-l)>>1);
	Build(rt<<1,l,mid);
	Build(rt<<1|1,mid+1,r);
	Pushup(rt);
}
void Pushdown(int rt)
{
	if(tr[rt].mark)
	{
		tr[rt<<1].date+=tr[rt].mark;
		tr[rt<<1|1].date+=tr[rt].mark;
		tr[rt<<1].mark+=tr[rt].mark;
		tr[rt<<1|1].mark+=tr[rt].mark;
		tr[rt].mark=0;
	}
}
int Search(int rt,int l,int r,int L,int R)
{
//	cout<<"l:"<<l<<" r:"<<r<<" L:"<<L<<" R:"<<R<<endl;
	if(L>R)
		return inf;
	if(L<=l&&r<=R)
		return tr[rt].date;
	int mid=l+((r-l)>>1);
	Pushdown(rt);
	int num=inf;
	if(L<=mid)
		num=min(num,Search(rt<<1,l,mid,L,R));
	if(mid<R)
		num=min(num,Search(rt<<1|1,mid+1,r,L,R));
	return num;
}
void Update(int rt,int l,int r,int L,int R,int c)
{
//	cout<<"l:"<<l<<" r:"<<r<<endl;
	if(L>R)
		return;
	if(L<=l&&r<=R)
	{
		tr[rt].date+=c;
		tr[rt].mark+=c;
		return;
	}
	Pushdown(rt);
	int mid=l+((r-l)>>1);
	if(L<=mid)
		Update(rt<<1,l,mid,L,R,c);
	if(mid<R)
		Update(rt<<1|1,mid+1,r,L,R,c);
	Pushup(rt);
}
void Dp()
{
	int now=0;
	for(int j=1;j<=n;++j)
	{
		f[j]=now+val[j];
		for(int p=head[j];p;p=edge[p].nxt)
		{
			int v=edge[p].to;
			now+=pay[v];
		}
	}
	int ans=f[n];
//	for(int i=1;i<=n;++i)
//	{
//		printf("%d ",f[i]);
//	}
	for(int i=2;i<=k;++i)
	{
		Build(1,1,n);
		for(int j=1;j<=n;++j)
		{
			f[j]=Search(1,1,n,1,j-1)+val[j];
		//	cout<<f[j]<<" ";
			for(int p=head[j];p;p=edge[p].nxt)
			{
				int v=edge[p].to;
				Update(1,1,n,1,st[v]-1,pay[v]);
			}
		}
		ans=min(ans,f[n]);//cout<<"ans:"<<ans<<endl;
	}
	printf("%lld",ans);
}
void Init()
{
	scanf("%lld%lld",&n,&k);
	for(int i=2;i<=n;++i)
		scanf("%lld",&dis[i]);
	for(int i=1;i<=n;++i)
		scanf("%lld",&val[i]);
	for(int i=1;i<=n;++i)
		scanf("%lld",&range[i]);
	for(int i=1;i<=n;++i)
		scanf("%lld",&pay[i]);
	++n;++k;
	dis[n]=pay[n]=inf;
}
signed main()
{
	Init();
	Get();
	Dp();
	return 0;
}