的朴素DP 非常好写, 是一个类似 LIS的问题,使用前缀和优化
for(int i = 1;i <= n;++i){
cin>>sum[i];
sum[i] += sum[i - 1];//这里要记录的是前i个数的和
}
dp[0] = 1;//设0的时候方案数为1
for(int i = 1;i <= n;++i) {
for(int j = 0;j < i;++j)
if(sum[i] - sum[j] >= 0) //如果这一段的理智度可以接受
dp[i] += dp[j]; //判断大小,决定状态
dp[i] %= mod;
}
考虑优化 到 ,
if(sum[i] - sum[j] >= 0) //如果这一段的理智度可以接受
dp[i] += dp[j]; //判断大小,决定状态
dp[i] %= mod;
}
sum[i] - sum[j] >= 0
等价于 sum[i] >= sum[j]
因此我们dp[i] 需要加的是 所有 sum[j] 小于 sum[i] 对应的 dp[j] 的和
可以离散化sum[i], 然后用树状数组维护 对应的 dp[j] 的前缀和