脚本宝典收集整理的这篇文章主要介绍了P4310 绝世好题(DP),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
二进制拆分来考虑,设f[i]表示一个数第i位为1的最长长度,那么在处理数a时,如果它的第i位为1,那么可以从f[i]转移过来。取max{f[i]},作为a的序列最长长度,用这个最长长度来更新数a为1的位的f[i]。
语言描述有限,详见代码。
#include<cstdio>
#include<iostream>
using namespace std;
int n;
int f[50];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k=0;
int a; scanf("%d",&a);
for(int i=0;i<=30;i++){
if(a&(1<<i)){
k=max(f[i]+1,k);
}
}
for(int i=0;i<=30;i++){
if(a&(1<<i)){
f[i]=max(f[i],k);
}
}
}
int ans=0;
for(int i=0;i<=30;i++) ans=max(ans,f[i]);
PRintf("%d",ans);
return 0;
}
以上是脚本宝典为你收集整理的P4310 绝世好题(DP)全部内容,希望文章能够帮你解决P4310 绝世好题(DP)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。