tyvj2018 小猫爬山

之前做过一道题“破锣摇滚乐队”，把猫都编了号，每辆车只能装一些编号递增的猫，而且前一辆车的猫编号都比后一辆车小。那道题的DP状态是：f[i][j]表示装了前i只猫，使用了j辆车时第j辆车所剩空间的最大值。转移时，考虑第i只猫是新坐一辆车（从f[i-1][j-1]转移）还是坐第j辆车剩下的空位（从f[i-1][j]转移），当然要从某个子状态转移过来，必须保证这个子状态是存在的（f[i][j]存在就是说j辆车能够塞下前i只猫）

这个题，没有顺序的限制，所以无法直接套用那道题的状态。但n<=18,可以状态压缩。f[S][j]表示集合S中的猫坐在前j辆车中时，第j辆车剩下的最大空间。转移时枚举S中每一只猫即可。（不妨认为我们是从第一辆车开始依次装猫，装到第j辆的时候前面j-1辆车就不再考虑了）。最后从小到大找可行状态。

不过状态总数高达18*2^18,状态转移需要O（n），也就是说，总的时间复杂度为18*18*2^18，好虚....所幸，这个方法的特点是：对于相同的n,任何输入的循环次数相同，所以我在自己的电脑上随便造了一组n=18的数据。测试结果表明，1s内完全可以出解，所以就放心交上去了2333。确实能过，不过时间被搜索虐爆了....

#include<cstdio>

#include<cstring>

#include<ctime>

int f[1<<18][19];//about 5 Mib

int a[20];

int max(int a,int b){

    return a>b?a:b;

}

int main(){

   // double t1=clock();

    int n,w;scanf("%d%d",&n,&w);

    for(int i=0;i<n;++i)scanf("%d",a+i);

    int lim=1<<n;

    memset(f,0xc2,sizeof(f));//初始化-inf

    f[0][0]=0;

    for(int i=1;i<lim;++i){

        for(int k=1;k<=n;++k){

            for(int j=0;j<n;++j){

                if(i&(1<<j)){

                    if(f[i^(1<<j)][k]>=a[j])f[i][k]=max(f[i][k],f[i^(1<<j)][k]-a[j]);

                    if(f[i^(1<<j)][k-1]>=0)f[i][k]=max(f[i][k],w-a[j]);

                }

            }

        }

    }

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

        if(f[lim-1][i]>=0){

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

            break;

        }

    }

   // double t2=clock();

   // printf("%.3fs\n",(t2-t1)/CLOCKS_PER_SEC);

    return 0;

}

巴特西

tyvj2018 小猫爬山

最新文章

热门文章