ZOJ 3802 Easy 2048 Again 状态DP

zoj 上次的月赛题，相当牛的题目啊，根本想不到是状态压缩好吧

有个预先要知道的，即500个16相加那也是不会超过8192，即，合并最多合并到4096，只有2的12次方

所以用状态压缩表示前面有的序列组合，找到了符合的，就往上累加合并生成新状态，否则就添加到前面的状态的后面构成新状态，因为每一个的状态都由前一个所得，用滚动数组即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int dp[][*];

int A[];

int n;

int main()

{

    int ti;

    scanf("%d",&ti);

    while (ti--)

    {

        memset(dp,-,sizeof dp);

        scanf("%d",&n);

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

        {

            scanf("%d",&A[i]);

        }

        int pos=;

        int ans=;

        dp[][]=;

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

        {

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

            {

                if (dp[pos^][j]==-) continue;

                dp[pos][j]=max(dp[pos][j],dp[pos^][j]);

                ans=max(ans,dp[pos][j]);

                int t=j;

                int q=A[i]-;

                int sum=A[i];

                if ((t&q)==)

                {

                    int k=A[i];

                    while ((t&k))

                    {

                        sum+=k<<;

                        k<<=;

                    }

                    t&=~(k-);

                    t|=k;

                }

                else t=A[i];

                dp[pos][t]=max(dp[pos][t],dp[pos^][j]+sum);

                ans=max(ans,dp[pos][t]);

            }

            pos^=;

        }

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

    }

}

巴特西

ZOJ 3802 Easy 2048 Again 状态DP

最新文章

热门文章