绝世好题题解

最新推荐文章于 2022-07-14 15:29:51 发布

lpc大菜逼

最新推荐文章于 2022-07-14 15:29:51 发布

阅读量446

点赞数 2

分类专栏：数位DP 动态规划文章标签：动态规划

本文链接：https://blog.csdn.net/cqbz_lipengcheng/article/details/106941996

版权

本文探讨了一道被称为'绝世好题'的动态规划问题，讲解了状态定义、状态转移方程及解题原理。作者在实现郭老师的解题思路时遇到问题，代码未能通过所有测试用例，分析后发现更新状态的问题导致效率不高。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

我太难了：

今天gm讲了“绝世好题”。但神奇的事发生了，我的代码是按照郭老师的想法打的但是没A，最后发现错在了一个很珂学的地方。

1.状态：

dp[i][j]表示以第i个数结尾，在第i个数二进制表示下的第j位，的最长长度（好绕啊！！！）

2.状态转移方程：

1):ansx表示此时以第i个数结尾的最长长度

2):ansx = max(ansx, dp[j] + 1);//此时j一定要满足x & (1 << j)其意义为第i个数第j位为1。

3.原理：

因为题目要求是让相邻的数 ‘&’ 出来是1，所以我们不难发现我们只需要让此时的数二进制下第j为一，这样无论如何’&‘前面’&'起来都是1

代码：

#include <iostream>
#include <cstdio>
using namespace std;
long long n, dp[12885], m, _max = -100;
int main() {
   
	scanf("%lld", &n);
	for(int i = 1;i <= n; i++) {
   
		scanf("%lld", &m);
		long long ansx = 1;
		for(int j = 0;j <= 30; j++) {
   //0~30枚举x二进制下的位数
			if(m