【状态设计优化DP】P4310 绝世好题

逃离我推掉我的手 2024-03-29 15:59 41阅读 0赞

**不愧是绝世好题**

**和abc那道E一样，也是重新定义状态来优化转移复杂度的DP**

[**(56条消息) Atcoder Beginner Contest E - Work or Rest\_lamentropetion的博客-CSDN博客**][56_ Atcoder Beginner Contest E - Work or Rest_lamentropetion_-CSDN]

**这种其实就是通过转移方式的特殊性来设计状态，从而降低复杂度**

**其实我感觉降低复杂度优化就是因为某个地方比较特殊，然后根据这个特殊性来优化**

**还有一点就是关于子序列的DP一般都以a\[i\]结尾来定义**

**这题是我做过的唯一线性DP设计状态的时候没加阶段的DP了，所以有点哈希内味**

**这种DP妙妙题我还没怎么写过，只会笨笨的那种DP，感觉得多写这种DP了**

[P4310 绝世好题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P4310 _ - _ _ _ _luogu.com.cn]

题意：

![747cbc7c9b21d2cbf246b135616f80fc.png][]

思路：

首先就是每个人都会的暴力DP，像LIS那样，这样是n^2的，显然T飞了

我们来**重新设计状态**

考虑它的转移方式：当且仅当某一位两个数该位都是1时转移，因此我们定义dp\[i\]为最后一个数的第i位为1的最长长度

在加入某个数之前，我们遍历位统计出此时dp\[i\]的最大值

然后在加入这个数之后来转移

加入这个数之后，所有位都变成了那个统计出来的最大值+1，这样就转移好了

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    int n;
    int a[mxn],dp[32];
    void solve(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++){
            int mx=-1;
            for(int j=30;j>=0;j--){
                if((a[i]>>j)&1) mx=max(mx,dp[j]);
            }
            for(int j=30;j>=0;j--){
                if((a[i]>>j)&1) dp[j]=max(dp[j],mx+1);
            }
        }
        int mx=-1;
        for(int j=30;j>=0;j--) mx=max(mx,dp[j]);
        cout<<mx<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**总结：**

**怎么去定义状态：**

**考虑转移方式，根据转移方式的特殊性来定义状态**

**这道题在设计状态时没有考虑阶段，所以有点哈希的感觉，我愿称之为哈希DP(bushi**

**还有一点就是关于子序列的DP一般都以a\[i\]结尾来定义**

[56_ Atcoder Beginner Contest E - Work or Rest_lamentropetion_-CSDN]: https://blog.csdn.net/weixin_62528401/article/details/128709275?spm=1001.2014.3001.5501
[P4310 _ - _ _ _ _luogu.com.cn]: https://www.luogu.com.cn/problem/P4310
[747cbc7c9b21d2cbf246b135616f80fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/5554cd91a35c4c28a2210feb61ff494d.png