P4310 绝世好题按位DP

这名字可海星\(OvO\)

思路：\(DP\)

提交：2次（\(zz\)我竟然把三目运算符写错了\(QwQ\)）

题解：

按位进行\(DP\)：\(f[i]\)表示结尾的数字包括\(1<<i\)的最长合法序列的长度。所以每输进来一个数\(x\)，我们就可以尝试更新\(f[i]=max(\)所有的 \(f[i])\) 且 \(x\ and\ (1<<i)!=0\)。

没了。

代码

#include<cstdio>

#include<iostream>

#define ull unsigned long long

#define ll long long

#define R register int

using namespace std;

#define pause (for(R i=1;i<=10000000000;++i))

#define In freopen("NOIPAK++.in","r",stdin)

#define Out freopen("out.out","w",stdout)

namespace Fread {

static char B[1<<15],*S=B,*D=B;

#ifndef JACK

#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)

#endif

inline int g() {

	R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;

	if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;

} inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}

inline void gs(char* s) {

	register char ch; while(isempty(ch=getchar()));

	do *s++=ch; while(!isempty(ch=getchar()));

}

} using Fread::g; using Fread::gs;

namespace Luitaryi {

int n,f[32],ans;

inline void main() {

	n=g(); for(R i=1,x;i<=n;++i) { R tmp=0;

		x=g(); for(R i=0;i<=30;++i) tmp=max(tmp,((1<<i)&x?1:0)*f[i]+1);

		for(R i=0;i<=30;++i) f[i]=max(((1<<i)&x?1:0)*tmp,f[i]);

	} for(R i=0;i<=30;++i) ans=max(ans,f[i]); printf("%d\n",ans);

}

}

signed main() {

	Luitaryi::main();

	return 0;

}

2019.07.22

巴特西

P4310 绝世好题按位DP

思路：\(DP\)

提交：2次（\(zz\)我竟然把三目运算符写错了\(QwQ\)）

题解：

代码

最新文章

热门文章

巴特西

P4310 绝世好题 按位DP

思路：\(DP\)

提交：2次（\(zz\)我竟然把三目运算符写错了\(QwQ\)）

题解：

代码

最新文章

热门文章

P4310 绝世好题按位DP