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

不愧是绝世好题

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

(56条消息) Atcoder Beginner Contest E - Work or Rest_lamentropetion的博客-CSDN博客

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

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

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

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

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

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

题意：

思路：

首先就是每个人都会的暴力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]结尾来定义