HDU 5045 状压DP 上海网赛

比赛的时候想的是把n个n个的题目进行状压但这样不能讲究顺序，当时精神面貌也不好，真是挫死了

其实此题的另一个角度就是一个n个数的排列，如果我对n个人进行状压，外面套一个按题目循序渐进的大循环，那么，在当前做第i个题目，前i-1个题目已经做完，然后做完的人的状态为j， j可能是1110 1101 1011什么的（假设已经做了三道题），因为我这样就可以只管状态而不管顺序了，我只取这种状态下的最大值，他究竟是怎么个顺序排列我不用管

到此。。。好像问题就没有什么问题了，这种做法重复 m/n次最后把剩余的再跑一下就可以了，因为每次考虑第i个题的时候只和i-1有关，则用个滚动数组即可，比较麻烦的是每次要清空，只能说空间和时间不可兼得啊

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

double A[][];

int n,m;

double dp[][<<];

int main()

{

    int t,kase=;

    scanf("%d",&t);

    while (t--)

    {

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

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

            for (int j=;j<m;j++) scanf("%lf",&A[i][j]);

        }

        int ALL=<<n;

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

            dp[][i]=dp[][i]=;

        }

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

            dp[][<<i]=A[i][];

        }

        int p=;

        double ans=;

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

            p^=;

            for (int j=;j<=ALL;j++) dp[p][j]=;

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

                if (dp[p^][j]==) continue;

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

                    if ((<<k)&j) continue;

                    int nt=(<<k)|j;

                    if (nt==ALL-) nt=;

                    dp[p][nt]=max(dp[p][nt],dp[p^][j]+A[k][i]);

                    if (i==m-) ans=max(ans,dp[p][nt]);

                }

            }

        }

        printf("Case #%d: %.5lf\n",++kase,ans);

    }

}

巴特西

HDU 5045 状压DP 上海网赛

最新文章

热门文章