我们发现这个转移其实只与n的所有质因子的次幂的可重集有关
根据一个结论，我们知道了在n<=10^24是，本质不同的可重集个数为170000+
我们可以爆搜出所有的可重集，然后进行DP即可
代码：（第一次写双longlong压12位，感觉挺不错的）
#include
#include
#include
#include
题解：恶心分类讨论题
其实各种分类讨论都是可以过的
简单讲讲我自己的分类讨论
首先把含有###或##.后面的字符串断开
然后按照##*来进行分段
考虑每一个段，如果当前的干扰器个数大于等于2，就一定可以把这一段的干扰器全部拿完
否则就考虑一下几种情况：（假设此时的干扰器个数为0）
1、*..#...*..#
2、#*....#..*
3、#*...*..#
4、*..#....#*
5、*..#....#..*
6、*..#....#*.....#...#*
我们设 *#. 的情况为flg1， .#* 的情况为flg2
那么出现11、22、21的情况则可以拿到2个干扰器，进而拿完所有的干扰器
而出现12的情况（4）则只能拿一个，而出现情况（5）则无法通过此段
情况（6）就是情况（4）的嵌套
注意一下判断就行了
代码：（考试的时候少判了“if(flg1){now=2;return 1;}”以及开小了数组，100->20。。。难受）
#include
#include
#include
using namespace std;
#define N 3000005
char a[N];
int cnt,pos[N],sum[N],ans;
bool solve(int l,int r,int &now)
{if(now>=2)return 1;bool flg1=0,flg2=0;for(int i=l;i<=r;i++){if(a[i]=='*'){now++,ans=max(ans,now);if(flg1){now=2;return 1;}}if(now>=2)return 1;if(a[i]=='#')continue;if(i=2)now=sum[pos[i]-2]-(i-1),ans=max(ans,now);if(!flg)break;if(i
题解：利用取值分界点的单调性+单调队列来优化DP
首先发现空位只填-1或K是最优的
再发现真实答案一定是可以取完整个区间[1,n]的（如果a1或an为负数则向内缩进一步）
于是我们设f[j][i]表示在[1,i]中放了j个-1的小b的答案的最小值
那么我们真实答案就是sum[n]-j*(K+1)-f[j][n]（sum[n]表示1~n所有空位都填K的前缀和）
则有f[j][i]=min_{1~i}(max(f[j-1][k-1],sum[i]-sum[k]))
注意整个DP是主动放置-1来分段，而且我们的决策点只能是在偶数位上，如果奇数位上有负数，这个DP就会被强制分段
这就是O(n^3)的做法
考虑优化
我们要求的是两个值的max的最小值
我们猜测存在一个分界点o
使得k∈[1,o]时，max(f[j-1][k-1],sum[i]-sum[k])=sum[i]-sum[k]
k∈[o,i)时，max(f[j-1][k-1],sum[i]-sum[k])=f[j-1][k-1]
其实这也是显然的，因为sum[i]-sum[k]是关于k单调递减的，f[j-1][k-1]是关于k单调递增的（因为如果放置的-1数目不变，越到后面，小b的最大子段和就会越大）
我们再大胆猜测o是关于i单调递增的
因为若k∈[1,o]，则要满足条件sum[i]-sum[k]>=f[j-1][k-1]
移一下项sum[i]>=f[j-1][k-1]+sum[k]
由于sum[i]是递增的,sum[k]是递增的,f[j-1][k-1]也是递增的
所以当i=i+1之后，会有更多的k属于[1,o]这个区间
现在我们利用单调性维护出了分段点o
那么前半段的贡献可以通过维护sum[k]的前缀最大值来完成（现在的目的是求sum[i]-sum[k]的最小值）
后半段的贡献可以通过单调队列来维护出f[j-1][k-1]的最小值
代码：（理论上来说可以直接维护分界点o来转移的，但是过不了对拍。。。）
#include
#include
#include
using namespace std;
#define N 10005
#define LL long long
const int INF=0x3f3f3f3f;
int a[N],q[N],he,ta;
int f[5005][N],sum[N];
int main()
{freopen("subsegment.in","r",stdin);freopen("subsegment.out","w",stdout);int n,K,i,j,k;scanf("%d%d",&n,&K);for(i=1;i<=n;i++)scanf("%d",&a[2*i-1]);n=2*n-1;a[1]=max(a[1],0);a[n]=max(a[n],0);for(i=1;i<=n;i++)sum[i]=sum[i-1]+(i&1?a[i]:K);memset(f,0x3f,sizeof(f));for(i=1,k=0;i<=n;i++){if(a[i]<0)k=i;f[0][i]=max(k?f[0][k-1]:0,sum[i]-sum[k]);}int ans=sum[n]-f[0][n],o,mx;for(j=1;j<=(n>>1);j++){ta=o=0,he=1,mx=-INF;for(i=1,k=0;i<=n;i++){if(a[i]<0)k=i,o=i-1,ta=0,he=1,mx=-INF;if(k<=i)f[j][i]=max(k?f[j][k-1]:0,sum[i]-sum[k]);if(k==i)continue;while(o+2<=i&&f[j-1][o+2-1]+sum[o+2]<=sum[i])o+=2,mx=max(mx,sum[o]);while(he<=ta&&o>=q[he])he++;f[j][i]=min(f[j][i],sum[i]-mx);if(he<=ta)f[j][i]=min(f[j][i],f[j-1][q[he]-1]);if(!(i&1)){while(he<=ta&&f[j-1][i-1]<=f[j-1][q[ta]-1])ta--;q[++ta]=i;}}ans=max(ans,sum[n]-j*(K+1)-f[j][n]);}printf("%d\n",ans);
}
