关于sosdp维护超集的疑问

CF1870E Bits And Pieces

第一篇题解dp的写法。

这是从小到大转移

CPP

void sos(int len){
	for(int i=0;i<21;i++)
		for(int j=0;j<len;j++)
			if(!(j&(1<<i))){
				update(j,mx[j^(1<<i)]);
				update(j,cx[j^(1<<i)]);
			}
	return ;
}

我的写法（从大到小）（通过了题目）：

CPP

void sos(int len){
	for(int i=0;i<21;i++)
		for(int j=len-1;j>=0;j--)
			if(!(j&(1<<i))){
				update(j,mx[j^(1<<i)]);
				update(j,cx[j^(1<<i)]);
			}
	return ;
}

疑问1：为什么从小到大是对的？用

dp[j \text{ xor }(1<<i])

来更新

dp[j]

，此时

dp[j \text{ xor }(1<<i)]

不一定是最优解吧。因为

dp[j \text{ xor }(1<<i)]

此时没有被更新过一次，只有初始时赋的值。

疑问2:我的从大到小的写法正确吗？因为没看到有题解这样写。

关于sosdp维护超集的疑问

讨论操作

回复

相关推荐

关于sosdp维护超集的疑问