这一章真是心态崩，剪枝太玄学啦，特别是那个搜索顺序我靠真的。。。

poj1011 枚举答案，搜索记录当前到第几根木棒。 剪枝：1、从大到小排序 2、排除等效，这个感觉还行，就是木棒按大小顺序进去，去除顺序不同的相同的情况，相同的木棒也是不用管的。  好的前面这些都可以想，关键是第三个，拼接第一个失败就全部重来。这个真是没想到

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int n,L,C,c[];

bool cmp(int x,int y){return x>y;}

bool v[];

bool dfs(int k,int len,int last)

{

    if(k==C+)return true;

    if(len==L)return dfs(k+,,);

    int fail=;

    for(int i=last+;i<=n;i++)

    {

        if(v[i]==false&&len+c[i]<=L&&c[i]!=fail)

        {

            v[i]=true;

            if(dfs(k,len+c[i],i))return true;

            v[i]=false;

            fail=c[i];

            if(len==)return false;

        }

    }

    return false;

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        if(n==)break;

        int sum=;

        for(int i=;i<=n;i++)

            scanf("%d",&c[i]), sum+=c[i];

        sort(c+,c+n+,cmp);

        int mmin=;

        for(int i=;i*i<=sum;i++)

            if(sum%i==)

            {

                if(i<mmin)

                {

                    L=i, C=sum/i;

                    memset(v,false,sizeof(v));

                    if(dfs(,,)==true)mmin=min(mmin,i);

                }

                if(sum/i<mmin&&i*i!=sum)

                {

                    L=sum/i, C=i;

                    memset(v,false,sizeof(v));

                    if(dfs(,,)==true)mmin=min(mmin,sum/i);

                }

            }

        printf("%d\n",mmin);

    }

    return ;

}

poj1011

poj1190 这题简直就是剪枝的代表作了。。。我可以算是想出了1.5+2？？个trick，但是这题整整五个剪枝啊！！！

1、大小，看到这个我都快条件反射了，管他有的没的倒序就是没错的

2、上下界，这个我想得还要复杂一点，导致有点难算，lyd就很暴力了直接开根

3、4、对于体积和表面积，到达目标的最小花费+当前花费比限制、当前最小花费大，那么就剪掉。我纠结了一会为啥一个叫可行性剪枝一个叫最优性剪枝，是因为体积是确定的而表面积是要求的

5、最***玄学的就是这个不等式了，上面全部的体积可以表示成sigema(1~dep-1)h[i]*r[i]^2，表面积就是2*sigema(1~dep-1)h[i]*r[i], 假设当前已经的体积为V

2*sigema(1~dep-1)h[i]*r[i] = 2/r[dep]*sigema(1~dep-1)h[i]*r[i]*r[dep] >= 2/r[dep]*sigema(1~dep-1)h[i]*r[i]*r[i] = 2*(N-V)/r[dep] 这个时候又可以判表面积。。。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

int N,m,mmin,r[],h[];

int minV[],minS[];

void dfs(int k,int V,int S)

{

    if(minV[k]+V>N)return ;

    if(minS[k]+S>mmin)return ;

    if(*(N-V)/r[k+]+S>mmin)return ;

    if(k==)

    {

        if(minV[k]+V==N)mmin=min(mmin,S);

        return ;

    }

    int Rli=min( int(sqrt(double(N-V+))) , r[k+]- );

    for(int R=Rli;R>=k;R--)

    {

        int Hli=min( (N-V)/(R*R) , h[k+]- );

        for(int H=Hli;H>=k;H--)

        {

            r[k]=R;h[k]=H;

            dfs(k-,V+R*R*H,S+*R*H+((k==m)?R*R:));

        }

    }

}

int main()

{

    scanf("%d%d",&N,&m);

    for(int i=;i<=m;i++)

        minV[i]=i*i*i+minV[i-], minS[i]=*i*i+minS[i-];

    mmin=;

    r[m+]=h[m+]=;

    dfs(m,,);

    printf("%d\n",mmin);

    return ;

}

poj1190

poj3076 状压，判点，判字母，绝望，留坟

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<bitset>

using namespace std;

int cnt;

char ss[][],sc[][][];

bitset<>mp[][],tt[][][],ts[][][];

void init()

{

    memset(mp,,sizeof(mp));

    for(int j=;j<=;j++)//行

    {

        int zt=;

        for(int i=;i<=;i++)

            if(ss[i][j]!='-')

                zt|=(<<(ss[i][j]-'A'));

        for(int i=;i<=;i++) mp[i][j]|=zt;

    }

    for(int i=;i<=;i++)//列

    {

        int zt=;

        for(int j=;j<=;j++)

            if(ss[i][j]!='-')

                zt|=(<<(ss[i][j]-'A'));

        for(int j=;j<=;j++) mp[i][j]|=zt;

    }

    for(int i=;i<=;i+=)

        for(int j=;j<=;j+=)

        {

            int zt=;

            for(int k=;k<=;k++)

                for(int l=;l<=;l++)

                    if(ss[i+k-][j+l-]!='-')

                        zt|=(<<(ss[i+k-][j+l-]-'A'));

            for(int k=;k<=;k++)

                for(int l=;l<=;l++)

                        mp[i+k-][j+l-]|=zt;

        }

    cnt=;

    for(int i=;i<=;i++)

        for(int j=;j<=;j++)

        {

            if(ss[i][j]=='-')cnt++;

            mp[i][j].flip();

        }

}

bitset<>p;bool v[];

bool check()

{

    for(int i=;i<=;i++)

        for(int j=;j<=;j++)

            if(mp[i][j]==&&ss[i][j]=='-')return false;

    for(int i=;i<=;i++)

    {

        p.reset();memset(v,false,sizeof(v));

        for(int j=;j<=;j++)

        {

            if(ss[i][j]!='-')v[ss[i][j]-'A']=true;

            else p|=mp[i][j];

        }

        for(int o=;o<=;o++)

            if(p[o]==&&v[o]==false)return false;

    }

    for(int j=;j<=;j++)

    {

        p.reset();

        for(int i=;i<=;i++)

        {

            if(ss[i][j]!='-')v[ss[i][j]-'A']=true;

            else p|=mp[i][j];

        }

        for(int o=;o<=;o++)

            if(p[o]==&&v[o]==false)return false;

    }

    for(int i=;i<=;i+=)

        for(int j=;j<=;j+=)

        {

            p.reset();memset(v,false,sizeof(v));

            for(int k=;k<=;k++)

                for(int l=;l<=;l++)

                {

                    if(ss[i+k-][j+l-]!='-')v[ss[i+k-][j+l-]-'A']=true;

                    else p|=mp[i+k-][j+l-];

                }

        for(int o=;o<=;o++)

            if(p[o]==&&v[o]==false)return false;

        }

    return true;

}

void influence(int x,int y)

{

    int o=ss[x][y]-'A';

    for(int j=;j<=;j++)mp[x][j][o]=;

    for(int i=;i<=;i++)mp[i][y][o]=;

    int i=((x-)/)*+,j=((y-)/)*+;

    for(int k=;k<=;k++)

        for(int l=;l<=;l++)

            mp[i+k-][j+l-][o]=;

}

bool bk;

void dfs(int k,int dep)

{

    if(bk==true)return ;

    memcpy(ts[dep],mp,sizeof(ts[dep]));

    memcpy(sc[dep],ss,sizeof(sc[dep]));

    bool qwq=true;

    while(qwq)

    {

        qwq=false;

        for(int i=;i<=;i++)

            for(int j=;j<=;j++)

            {

                if(ss[i][j]=='-'&&mp[i][j].count()==)

                {

                    k--;qwq=true;

                    for(int o=;o<=;o++)

                        if(mp[i][j][o]==)

                        {

                            ss[i][j]='A'+o;

                            influence(i,j);

                            break;

                        }

                }

            }

        for(int o=;o<=;o++)

        {

            for(int i=;i<=;i++)

            {

                int u=,jj;

                for(int j=;j<=;j++)

                    if(mp[i][j][o]==)

                    {

                        u++;jj=j;

                        if(u==)break;

                    }

                if(u==)

                {

                    ss[i][jj]='A'+o;

                    influence(i,jj);

                }

            }

            for(int j=;j<=;j++)

            {

                int u=,ii;

                for(int i=;i<=;i++)

                    if(mp[i][j][o]==)

                    {

                        u++;ii=i;

                        if(u==)break;

                    }

                if(u==)

                {

                    ss[ii][j]='A'+o;

                    influence(ii,j);

                }

            }

            for(int i=;i<=;i+=)

                for(int j=;j<=;j+=)

                {

                    int u=,ii,jj;

                    for(int k=;k<=;k++)

                        for(int l=;l<=;l++)

                        {

                            if(mp[i+k-][j+l-][o]==)

                            {

                                u++;ii=i;jj=j;

                                if(u==)break;

                            }

                        }

                    if(u==)

                    {

                        ss[ii][jj]='A'+o;

                        influence(ii,jj);

                    }

                }

        }

    }//必定赋值

    if(!check())

    {

        memcpy(mp,ts[dep],sizeof(mp));

        memcpy(ss,sc[dep],sizeof(ss));

        return ;

    }

    if(k==)

    {

        bk=true;

        for(int i=;i<=;i++)

        {

            for(int j=;j<=;j++)printf("%c",ss[i][j]);

            printf("\n");

        }

        return ;

    }

    int cc=,nx,ny;

    for(int i=;i<=;i++)

        for(int j=;j<=;j++)

            if(ss[i][j]=='-'&&mp[i][j].count()<cc)

            {

                cc=mp[i][j].count();

                nx=i,ny=j;

            }

    for(int o=;o<=;o++)

        if(mp[nx][ny][o]==)

        {

            memcpy(tt[dep],mp,sizeof(tt[dep]));

            ss[nx][ny]='A'+o;

            influence(nx,ny);

            if(check())

                dfs(k-,dep+);

            ss[nx][ny]='-';

            memcpy(mp,tt[dep],sizeof(mp));

        }

    memcpy(mp,ts[dep],sizeof(mp));

    memcpy(ss,sc[dep],sizeof(ss));

}

int main()

{

    for(int i=;i<=;i++)scanf("%s",ss[i]+);

    init();

    bk=false;dfs(cnt,);

    return ;

}

poj3076(TLE)

最新文章

  1. Quartz
  2. 设置时间&amp;时区
  3. 字符集与编码01--charset vs encoding
  4. 13.代理模式(Proxy Pattern)
  5. .net学习之委托和事件
  6. 对线性回归，logistic回归和一般回归的认识
  7. Unix编程之size_t、ssize_t
  8. ListView item 中TextView 如何获取长按事件
  9. Java基础知识强化之集合框架笔记41：Set集合之HashSet存储自定义对象并遍历练习
  10. Catenyms
  11. H面试程序（10）： 字符串包含问题
  12. C# 导出 excel 复杂格式 html导出
  13. 华为G520联通版刷机包 基于MIUI CM11新 平稳 稳定
  14. Facebook兆级别图片存储及每秒百万级别图片查询原理
  15. linux下实用的快速随机生成复杂密码
  16. [系统集成] RT（Request Tracker）执行自定义脚本及发送微信、短信的实现方法
  17. Sicily T-primes
  18. python基础学习（二）注释和算术运算符
  19. IIS 安全设置
  20. （转）面向对象——UML类图设计

热门文章

  1. Centos7下Docker的使用
  2. RawURL
  3. Vs2010无法打开文件“Kernel32.lib”、无法打开“libcpmt.lib”"msvcprt.lib"
  4. ES: 机器学习、专家系统、控制系统的数学映射
  5. DP:***24种设计模式--转自刘伟
  6. mysql的模糊查询
  7. 洛谷P2894 [USACO08FEB]酒店Hotel_区间更新_区间查询
  8. NOIP2018提高组省一冲奖班模测训练（六）
  9. SSM知识巩固
  10. wcf的Contract中name的使用