[BZOJ4300] 절세의 좋은 문제, 비트 연산 관련 DP

전송문은 앞에 적혀 있다. 길이 멀고 아득한 사고방식: 정확히 말하자면 나는 이 문제를 처음 봤을 때 사고방식이 명확하지 않았다. 항상 a[i]&a[j]=0의 상황을 먼저 처리해야 한다고 생각했고 저녁에 집에 돌아와서 반나절을 공상했지만 생각해 내지 못했다.아침에 기관실에 와서야 정해에 가까운 생각을 했어요. 전에 쓴 상승자 서열을 봤는데 이 문제도 그런 것 같아요.단지 2진법의 한 분에 따라 DP를 할 수 있다. 1이면 f의 최대치를 비교할 수 있다. (0이면 반드시 이 분에서 옮길 수 없다) 마지막으로 1의 자리에 있는 f는 최대치 +1에서 원시 DP 방정식을 옮길 수 있다. f[i]=max(f[j]+1)j=1...i-3 초기화: f[i]=1 주의: 코드가 너무 짧은데 눌린 것 같아...미안해.

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int f[100002];
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int x,maxn=0;
        scanf("%d",&x);
        for (int j=1,t=x;t;t>>=1,j++)
            if (t&1) maxn=max(maxn,f[j]);
        for (int j=1,t=x;t;t>>=1,j++)
            if (t&1) f[j]=max(maxn+1,f[j]);
    }
    for (int i=1;i<=n;i++) ans=max(f[i],ans);
    printf("%d",ans);
}