最开始很容易想到设\(f[i][j][k]\)表示区间\([i,j]\)合并出\(k\)是否可以,显然复杂度爆炸
这样做的问题是什么?
冗余状态太多了!题目只关心给的那一个\(t\),我们只用想如何达到这个\(t\)即可
既然这样,我们考虑最终这个数是怎么来的,手动模拟一下
设有五个数A B C D E
最开始合并C
和D
,有A B C-D E
然后再让B
减去后面这一个数,有A B-C+D E
然后我们就可以发现,在某一个时刻,如果有一个元素的值等于$$\sum_{k=i}^{j}±a_k$$,此时我们让这个元素的前面一个元素减去这个元素,那么这个元素里面所有的正负号全部取反
于是我们就可以知道,最终这个数很可能长成这个样子:$$a_1-a_2+\sum_{k=3}^{n}±a_k$$
为什么\(a_1\)前面一定是加号,\(a_2\)前面一定是减号,由上面的分析是很显然的
于是我们做一个01背包就可以判断是否能够合并出给定数字了
题目要求输出方案,我们假设现在已经拿到了一个方案,我们看看能不能一定找到一个步骤,使得这些步骤是合法的
对于任意一个方案,从左往右最开始一定是由若干个减号组成的,我们找到这一段的最后一个减号(即这个方案的第一个加号的前面一个减号),然后我们去掉这个减号表示最后一步操作是这个减号,然后这个减号后面的所有符号全部取反,再把这个减号前面的所有减号从左到右依次去掉,注意此时去掉的时候就是先去掉的先操作了,操作完后剩下的符号一定是由一段连续的减号开头的,就又回到上面的情况了
写成数学归纳法就是:
标签:这个,一个,元素,减号,操作,去掉,我们 From: https://www.cnblogs.com/dingxingdi/p/17973555