搜索
简帛阁>技术文章>NOIP2016Day2T3愤怒的小鸟(状压dp) O(2^n*n^2)再优化

NOIP2016Day2T3愤怒的小鸟(状压dp) O(2^n*n^2)再优化

  看这范围都知道是状压吧。。。

  题目大意就不说了嘿嘿嘿

  网上流传的写法复杂度大都是O(2^n*n^2),这个复杂度虽然官方数据可以过,但是在洛谷上会TLE【百度搜出来前几个博客的代码交上去都TLE了】,于是造成了洛谷上这题提交5k3只AC了250人,AC率只有4.7%。。。【这么卡常真的丧病,还是因为老爷机?

  所以我就写写怎么优化吧OWO

  首先还是先求出两两猪的解析式和能穿过多少只猪,记得如果两个猪的横坐标相同就要continue,a和b的公式随手推一推。然后枚举状态数,再枚举哪两只猪被射,记得处理只射一只猪的情况。

  f[i|num[j][k]]=min(f[i|num[j][k]],f[i]+1);【num[j][k]为一只穿过第j只猪和第k只猪的鸟发射后的状态

  这就是(2^n*n^2)的写法,接下来优化。

  对于我们枚举的每一个状态i,我们找到它正数第一只没射掉的猪进行转移后break。

  因为如果我们转移了第一只后面的没射的猪,到时候还要回头来将第一只猪射掉,所以后面的没射的猪的转移其实是多余的,射完第一只猪后接着往后射就可以了。

  【当然只用正数第二只猪或者第三只猪或第四只或第五只转移都是可以的,一个道理。。。显然第一只最好写吧233

  优化之后就可以过洛谷的这题辣。

代码如下:

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,t,num[20][20],f[1048576];
double x[20],y[20];
bool same(double x,double y){return fabs(x-y)<1e-6;}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)num[i][j]=0;
        for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
        {
            if(same(x[i],x[j]))continue;
            double a=(y[j]/x[j]-y[i]/x[i])/(x[j]-x[i]);
            if(a>=0)continue;
            double b=y[i]/x[i]-a*x[i];
            for(int k=1;k<=n;k++)
            if(same(a*x[k]+b,y[k]/x[k]))num[i][j]|=(1<<(k-1));
        }
        for(int i=0;i<=(1<<n)-1;i++)f[i]=233333333;f[0]=0;
        for(int i=0;i<=(1<<n)-1;i++)
        for(int j=1;j<=n;j++)
        if(!(i&(1<<(j-1))))
        {
            for(int k=j;k<=n;k++)
            {
                if(j==k)f[i|(1<<(j-1))]=min(f[i|(1<<(j-1))],f[i]+1);
                if(same(x[j],x[k]))continue;
                f[i|num[j][k]]=min(f[i|num[j][k]],f[i]+1);
               }
               break;
       }
        printf("%d\n",f[(1<<n)-1]);
    }
}
View Code
这范围都知道是状压吧。。。题目大意就不说了嘿嘿嘿网上流传写法复杂度大都是O(2^n*n^2),这个复杂度虽然官方数据可以过,但是在洛谷上会TLE【百度搜出来前几个博客代码交上去都TLE了】,于是
传送门DescriptionKiana最近沉迷于一款神奇游戏无法自拔。简单来说,这款游戏是在一个平面上进行。有一架弹弓位于$(0,0)$处,每次Kiana可以用它向第一象限发射一只红色小鸟小鸟
~~题面~~~题解:首先观察数据范围,n<18,很明显是状压DP。所以设f[i]表示状态为i时最小代价。然后考虑转移。注意到出发点(0,0)已经被固定,因此只需要2点就可以确定一条抛物线,所
当年两个压轴题现在都随便做了呢w原题:n<18,t<5我当时怎么就不会系列233一看这数据范围,欸呀壮鸭低劈预处理出任意两个猪能够确定抛物线方程,最多只有153个,然后检查他们能够扫
【题意】UniversalOnlineJudge【算法】状态压缩型DP【题解】看数据范围大概能猜到是状压了。根据三点确定一条抛物线,枚举两个点之间抛物线,枚举有多少点在抛物线上(压缩为状态c[])
$O(n*3^n)$好难想还有好多没见过操作令$f[i][j]$表示最深深度为i,点状态为j最小代价,每次枚举状态$S$后,计算$S$补集里每个点与S里最小连边代价,$O(3^n)
最大子矩阵TimeLimit:30000/10000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):289
状态压缩dp可太难了但大体上和状态机感觉适基于差不多思想这种dp除了能够用某种图形不重叠地填满一张图还可以用于检测是否所有的要求都达到了状态(这话说的我自己都不知道在说什么https://wwwl
importjavautilScanner;/***迪杰斯特拉算法:单源点到其他点最短路径及距离*/publicclassPtest{//不能设置为IntegerMAX_VALUE,否则两个Int
被“if(ab)”坑了QAQ。。。写C++还是得开Warning,这么久了pascal还没改过来咋回事啊QWQ题目大意就不说了OWO网上题解都不怎么看得懂啊。。。好像写得都很乱?还是我太sb了f[