luogu P3146 （区间dp）

叁歲伎倆 2021-11-01 09:10 525阅读 0赞

[传送门][Link 1]

# 题意： #

有一行格子，每个格子都有一个数值，如果相邻两个格子相同的话，可以合并成一个新的格子，新的格子的值为原来的值+1。现在问你通过不断的合并，最后最大能够的值的大小。

# 分析： #

相邻区间可以合并，故我们不难想到可以用区间dp去解决。我们可以设\\(dp\[l\]\[r\]\\)为区间\\(\[l,r\]\\)能够合并出来的最大的值。但是这个题相对于一般的区间dp还存在着相邻的格子必须要相等的制约，因此我们在枚举划分节点\\(k\\)的时候，还需要判断一下划分出来两个子区间的能够合并出来的最大的值是否相同，如果相同才进行\\(+1\\)的更新。因此整体的状态转移方程为：\\\[dp\[l\]\[r\]=\\max(dp\[l\]\[r\],dp\[l\]\[k\]+1)\\&(dp\[l\]\[k\]==dp\[k+1\]\[r\])\\\]

最后，需要注意的是，最终的答案不一定是\\(dp\[1\]\[n\]\\)。因此这个题目的特殊性（需要相邻两个节点相同才能合并），因此区间\\(\[1,n\]\\)不一定能够合并，因此，我们还需要在状态转移的过程中记录一下最大值才行。整体的时间复杂度为：\\(\\mathcal\{O\}(n^3)\\)。

# 代码： #

#include <bits/stdc++.h>
    #define maxn 300
    using namespace std;
    int dp[maxn][maxn];
    int a[maxn],maxx;
    int main()
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
        }
        for(int i=1;i<=n;i++){
            dp[i][i]=a[i];
            maxx=max(dp[i][i],a[i]);
        }
        for(int p=1;p<=n;p++){
            for(int i=1,j=i+p;i<=n&&j<=n;i++,j=i+p){
                for(int k=i;k<j;k++){
                    if(dp[i][k]==dp[k+1][j]){
                        dp[i][j]=max(dp[i][j],dp[i][k]+1);
                    }
                }
                maxx=max(maxx,dp[i][j]);
            }
        }
        printf("%d\n",maxx);
        return 0;
    }

转载于:https://www.cnblogs.com/Chen-Jr/p/11212590.html

[Link 1]: https://www.luogu.org/problemnew/show/P3146