首页 > 代码库 > ZOJ 3802 Easy 2048 Again 状态DP

ZOJ 3802 Easy 2048 Again 状态DP

2024-07-20 09:30:45   216人阅读

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

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

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

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;int dp[2][4097*2];int A[510];int n;int main(){    int ti;    scanf("%d",&ti);    while (ti--)    {        memset(dp,-1,sizeof dp);        scanf("%d",&n);        for (int i=1; i<=n; i++)        {            scanf("%d",&A[i]);        }        int pos=1;        int ans=0;        dp[0][0]=0;        for (int i=1; i<=n; i++)        {            for (int j=0; j<4096*2; j++)            {                if (dp[pos^1][j]==-1) continue;                dp[pos][j]=max(dp[pos][j],dp[pos^1][j]);                ans=max(ans,dp[pos][j]);                int t=j;                int q=A[i]-1;                int sum=A[i];                if ((t&q)==0)                {                    int k=A[i];                    while ((t&k))                    {                        sum+=k<<1;                        k<<=1;                    }                    t&=~(k-1);                    t|=k;                }                else t=A[i];                dp[pos][t]=max(dp[pos][t],dp[pos^1][j]+sum);                ans=max(ans,dp[pos][t]);            }            pos^=1;        }        printf("%d\n",ans);    }}

 

ZOJ 3802 Easy 2048 Again 状态DP


联系
我们