@[chen_zhe](/space/show?uid=8457)
by xsgqwxj @ 2019-10-24 20:01:30
我拿了第二个题解拍了一遍答案是3(手推也是)但第一个题解答案是-1
by xsgqwxj @ 2019-10-24 20:03:42
3
3
1 -1 1
0 1 -1
0 0 1
(来自tlnllkbp的讨论的数据)
by xsgqwxj @ 2019-10-24 20:05:00
(害得我花1.5h证明他的正确性,和老师讨论了很久,又花了一会儿时间找反例(不过我没找出来……))
by xsgqwxj @ 2019-10-24 20:08:06
对哦
by 清平乐 @ 2019-10-25 19:49:55
我有个同学用的DP也输出了-1
我用BFS就是3
by 清平乐 @ 2019-10-25 19:50:54
我找到错了
---第一篇题解
```cpp
for(RI i=(1<<n)-1;i>=0;i--)
{
for(RI j=1;j<=m;j++)
{
int now=i;
for(RI l=1;l<=n;l++)
{
if(a[j][l]==0)continue;
if(a[j][l]==1 and (i&(1<<(l-1)))) now^=(1<<(l-1));
if(a[j][l]==-1 and !(i&(1<<(l-1)))) now^=(1<<(l-1));
}
f[now]=std::min(f[now],f[i]+1);
```
他在DP时不清楚f[now],f[i]的大小关系
他要保证在求f[now],f[i]已经求出来了
然而f[now]在经过一次开关灯操作后i可能变的比now大也可能小,由于题解中是逆序枚举的,所以必须保证i比now要大(但好像测试数据比较水,不存在这种情况)
by 清平乐 @ 2019-10-25 20:27:04
@[文科生!](/space/show?uid=224358)
对啊
我想的是用之前的状态推这个状态
但我这样也会存在使用未求解的状态转移的情况
by lqhsr @ 2019-10-31 19:26:21
不知您有何妙计
by lqhsr @ 2019-10-31 19:26:32
@[xsgqwxj](/space/show?uid=33611)
@[文科生!](/space/show?uid=224358)
by lqhsr @ 2019-10-31 19:26:55