题目内容

P3416

大意:在一串序列上玩 2048,规则是能合并相邻两个数然后变成这个数加一,求能合并出来的最大数

解题思路

区间 dp,但是要注意一些细节:

  • 如果待合并的两个区间都为 0,那么不能进行更新,否则会被讨论区的 Hack 数据 Hack 掉
  • 区间长为 1 的时候也要预处理答案,还是 Hack
  • 答案不是 f[1][n],因为你可能根本合并不到

具体的实现还是枚举区间长度和断点,如下:

#include <cstdio>

inline int max(int a,int b)
{
    return a>b?a:b;
}

const int maxn=248+10;
int f[maxn][maxn],n;

int main()
{
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;i++)
        scanf("%d",&f[i][i]),ans=max(ans,f[i][i]);//这里要提前预处理好答案
    for(int len=2;len<=n;len++)
        for(int i=1,j=i+len-1;j<=n;i++,j++)
            for(int k=i;k<j;k++)
            {
                if(f[i][k]==f[k+1][j] && f[i][k] && f[k+1][j])//一定要不为0
                    f[i][j]=f[i][k]+1;
                ans=max(ans,f[i][j]);//每次合并都要统计答案
            }
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年3月11日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。