优化dp

Vanity_ · 2019-08-16 19:39:44 · 个人记录

背景

有些时候dp的时间复杂度和空间复杂度很高不符合题目要求,这时候我们就会想尽一切办法去卡常优化.下面我就来学习(复习)一下dp的优化

正题

状态压缩DP

背景

我们来看看这道题目P1879 玉米田Corn Fields

这道题的状态有很多种普通的搜索完全做不到.

前置知识

位运算想必大家都学过,但有些同学没学,所以我在这简单阐述一下.

| 按位或 把一个数拆成二进制 把每一位进行或的运算返回十进制的值如2(10)|1(01)=3(11)

& 按位或 把一个数拆成二进制 把每一位进行与的运算返回十进制的值如5(101)&3(011)=1(001)

^ 按位异或 把一个数拆成二进制 相同位置不同为1相同为0 5(101)^1(001)=4(100)

>> 右移 如x>>y相当于x/(2^y)向下取整 9(1001)>>1=4(100)

<< 左移 如x<<y相当于x*2^y 5(101)<<1=10(1010) 2(10)<<2=8(1000)

使用

依然是那道题

我们用普通dp试试

我们很容易得出状态转移方程 $dp[i][k]=\Sigma^{j=1}_{j<=cnt} dp[i-1][j]$(j的状态与i-1行能放牧的地方不冲突且与k的状态不冲突) 问题是如何储存这个状态? 我们发现能不能放牧用01表示放不放牧也可以用10表示. 这不就是二进制吗! 但又出现了一个问题我们如何处理冲突别急着往下看先思考一下 ~~~ 防偷窥 ~~~~ 其实判断这个状态是否与自己冲突很简单就是x&(x<<1) 如果是0就不冲突可以手动模拟一下那么怎么判断放牧区与草地不冲突呢样例是 ~~~ input: 2 3 1 1 1 0 1 0 output: 9 ~~~ 我们把可以种草的地方取反一下变成了 ~~~ 0 0 0 1 0 0 ~~~ 那么我们只需将这个放牧状态与取反后的状态按位与一下就可以啦,如果不冲突就一定是0啦! 判断上一行的状态是否与当前状态冲突也很简单就是把两个状态按位与一下,如果等于0就不冲突,否则就冲突啦! 综上我们可得出代码 ~~~cpp #include <cstdio> const int mod=100000000; int map[13];//储存能种草的地方 int can[1<<12|1]; int dp[13][1<<12|1]; int main() { int n,m; int ans=0,i,j,o,tot,cnt=0,k; scanf("%d%d",&n,&m); tot=1<<m;//所有状态种类 for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&o); if(!o) map[i]|=1<<(m-j);//取反 } for(i=0;i<tot;i++) if((!(i&(i<<1)))) can[++cnt]=i;//cnt为可行状态数 for(i=1;i<=cnt;i++) if((!(map[1]&can[i])))dp[1][can[i]]=1;//先预处理第一行的状态 for(i=2;i<=n;i++) for(j=1;j<=cnt;j++) if(((map[i-1]&can[j])==0))//判断是否与可以种草处冲突 for(k=1;k<=cnt;k++) if(((map[i]&can[k])==0)&&((can[j]&can[k])==0)) dp[i][can[k]]=dp[i][can[k]]+dp[i-1][can[j]]%mod; for(i=1;i<=cnt;i++) ans=(ans+dp[n][can[i]]%mod)%mod; printf("%d",ans); } ~~~ 这是比较简单的状压dp ### 一些习题因为本人实力有限所以没有提升训练想要学好一种算法当然要练习啦! 别看他们的难度很难什么提高+ 省选-,省选/noi-,大部分都比较简单 [P2051](https://www.luogu.org/problem/P2051) [P1896](https://www.luogu.org/problem/P1896)~~(打表大法好)~~ [P2704](https://www.luogu.org/problem/P2704) ### 总结虽然状态压缩可以优化dp的时间,空间复杂度但是只能用于要求存状态的~~毒瘤~~dp这就是它的局限性.有时候我们还是得打正解,不要抱有任何侥幸心理. ## 单调队列优化dp ### 背景我们先看一下这道题目[P1886 滑动窗口](https://www.luogu.org/problem/P1886) 这道题怎么做读者：我会线段树！那么数据调成$n<=10^8$怎么做读者:emm... ### 前置知识单调队列，即单调递减或单调递增的队列。那么问题来了队列不是尾进头出吗怎么维护单调性呢? 我们灵活变通一下让队首可进可出,让队尾也可进可出不就行了吗? 没看懂的同学可以看一下代码 ~~~ cpp //此操作单调递减 for(i=1;i<=n;i++)//a数组是要插入的数组,n为他的长度 { while(head<=tail&&que[tail]<=a[i]) tail--; //这里取等于号的原因可以理解为一个oier比你小还比你强或一样强你就打不过他了QWQ que[++tail]=a[i]; } ~~~ ### 使用依然是那个例题我们先打一个普通的dp $f[i]$ 表示以i结尾的窗口中的最大(小)值则 $f[i]$=$\Sigma^{j=i-k+1}_{j<=i}$ $min(f[j])

这个时间复杂度可是O(n^2)!

难不成你能降一维?你以为单调队列了不起啊.

没错单调队列就是可以为所欲为!

打完暴力DP代码我们发现大部分的时间都浪费在寻找(i-k+1~i)中的最小值上.

找最小值我们思考一下发现堆似乎能解决这个问题可是我要求的数据范围是n<=10^8

堆虽然比线段树的解法要更优秀但是还是很难过我的毒瘤数据.

别忘了我们刚刚学了单调队列所以这道题目就可做了

每次加入a[i],当i>=k时取出队首然后输出假设队首的位置不在区间内就弹出 ~~(就好像你太老了必须退役)~~

这样我们就能愉快的写代码了~

#include <bits/stdc++.h>
using namespace std;
int num[1000001],p[1000001],a[1000001];
int k,head,tail,n;
void dpmin()
{
    int i;
    head=0;
    tail=1;
    for(i=1;i<=n;i++)
    {
        while(num[head]<=i-k&&head<=tail) ++head;
        while(a[i]<=p[tail]&&head<=tail) --tail;
        p[++tail]=a[i];
        num[tail]=i;
        if(i>=k) printf("%d ",p[head]);
    }
    printf("\n");
}
void dpmax()
{
    int i;
    head=0;
    tail=1;
    for(i=1;i<=n;i++)
    {
        while(num[head]<=i-k&&head<=tail) ++head;
        while(a[i]>=p[tail]&&head<=tail) --tail;
        p[++tail]=a[i];
        num[tail]=i;
        if(i>=k) printf("%d ",p[head]);
    }
}
int main()
{
    int i;
    scanf("%d%d",&n,&k); 
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    dpmin();
    dpmax();
}

读者:好吧,我承认有时候单调队列可以为所欲为,但是为什么它是O(N)的呢?

因为每个元素都只进出队列最多一次所以是O(N)的啦!

你如果还不承认单调队列的强大的话那么我们进入一个毒瘤题目

提升训练

毒瘤题目

~~为了找这个题目我找了极其之久~~

读者:这个题目看起来什么都不像啊,数据范围又这么毒瘤.

如果我们考虑暴力的话那么时间复杂度是O(N^2)的显然不能AC

现在我们定义oil[i]为第i号车站有的油量dis[i]为第i号车站juli到i+1号的车站的距离.b[i]为oil[i]-dis[i] sum[i]为

\Sigma^{j=1}_{j<=i}$$b[i]

(由于是个环所以要开两倍空间)

看出来了吗?

我们只要求

\Sigma^{j=i}_{j<=i+n-1}

min(sum[j]-sum[i-1])$看它是不是负数就,如果不是将$OK[i]=1

所以我么可以维护一个单调递增的单调队列来维护最小的sum[j]每次插入sum[i+n-1]每次删除sum[i-1]的值就可以了

这是顺时针之后再反过来跑一遍就可以了

#include <bits/stdc++.h>
using namespace std;
long long oil[2000001];
long long dis[2000001];
long long sum[2000001];
long long b[2000001];
bool ok[2000001];
struct
{
    long long data;
    int no;
}que1[2000001],que2[2000001];
int main()
{
    int n,i,head1=1,tail1=0,head2=1,tail2=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        sdpcanf("%lld%lld",&oil[i],&dis[i]);
        oil[i+n]=oil[i];
        dis[i+n]=dis[i];
        b[i]=oil[i]-dis[i];
        b[i+n]=b[i];
    }

    for(i=1;i<=n*2;i++)
        sum[i]=sum[i-1]+b[i];
//  sum[1]=0;
    for(i=1;i<=n;i++)
    {
        while(head1<=tail1&&sum[i]<=que1[tail1].data) tail1--;
        que1[++tail1].data=sum[i];
        que1[tail1].no=i;
    }
    for(i=1;i<=n;i++)
    {
    //  while(que1[head1].no<i&&head1<=tail1) head1--;
        while(head1<=tail1&&sum[i+n-1]<=que1[tail1].data) tail1--;
        que1[++tail1].data=sum[i+n-1];
        que1[tail1].no=i+n-1;
        if(que1[head1].no==i-1) head1++;
        if(que1[head1].data>=sum[i-1]) ok[i]=1;
    }
    memset(sum,0,sizeof(sum));
    b[1]=b[1+n]=oil[1]-dis[n];
    for(i=2;i<=n;i++)
        b[i]=b[i+n]=oil[i]-dis[i-1];
    sum[0]=0;
    for(i=1;i<=n*2;i++)
        sum[i]=b[i]+sum[i-1];
//  sum[1]=0;
    for(i=0;i<n;i++)
    {
        while(head2<=tail2&&sum[i]>=que2[tail2].data) tail2--;
        que2[++tail2].data=sum[i];
        que2[tail2].no=i;
    }
    for(i=1;i<=n;i++)
    {
//      while(head2<=tail2&&que2[head2].no<i) head2--;
        while(head2<=tail2&&sum[i-1+n]>=que2[tail2].data) tail2--;
        que2[++tail2].data=sum[i-1+n];
        que2[tail2].no=i-1+n;
//      printf("%lld ",que2[head2].data);
        if(que2[head2].no==i-1) head2++;
        if(que2[headxinl2].data<=sum[i+n]) ok[i]=1;
    }
    for(i=1;i<=n;i++)
    {
        if(ok[i]) printf("TAK\n");
        else printf("NIE\n");
    }
}

~~我调了1天QAQ~~

一些习题

想要学好一种算法当然要练习啦!

跳房子

牛的阵容Cow Lineup

挤奶牛Crowded Cows

其实你在洛谷里面搜一下单调队列的算法标签就有很多题啦!

总结

我们发现这个单调队列我们只能对含有min(max)的状态转移方程进行优化

所以我在这承认单调队列确实不能为所欲为

虽然有时候它非常的快但有时候会被卡常如Bzoj1531他的速度因为常数问题比状态压缩dp慢的多!

最后的总结

这些优化都非常难以调试所以我们在考试时遇到这种题尽量先跳过~~(除了后面的题目更毒瘤)~~,有的时候dp不一定是正解所以我们要懂得放弃,不要妄想卡常,优化可以卡过,该打正解还是要打,正如LC所说dp其实就是比普通暴力更优的暴力.