一站式企业服务平台是什么,龙华区住房和建设局网站,牌具网站广告怎么做,包头网站建设哪家好【题目来源】http://oj.ecustacm.cn/problem.php?id1781http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 给你一个长度为 n 的序列#xff0c;序列中的元素只包括 1 和 -1。 请问有多少个连续的子序列乘积为正数。【输入格式】 输入第一行为正整数 n。#xff08;n…【题目来源】http://oj.ecustacm.cn/problem.php?id1781http://oj.ecustacm.cn/viewnews.php?id1023【题目描述】 给你一个长度为 n 的序列序列中的元素只包括 1 和 -1。 请问有多少个连续的子序列乘积为正数。【输入格式】 输入第一行为正整数 n。n不超过10^6 第二行包含 n 个整数。【输出格式】 输出一个数字表示答案。【输入样例】 4 1 1 -1 -1【输出样例】 6【算法分析】 ● 动态规划 最后一步法https://blog.csdn.net/hnjzsyjyj/article/details/112797538 本题是“计数型”问题可采用动态规划算法求解。 1确立状态 设输入的序列是 a[1]~a[n]依据最后一步法可定义 DP 状态为f[i][0]以 a[i] 结尾的积为 -1 的连续子序列个数 f[i][1]以 a[i] 结尾的积为 1 的连续子序列个数例如针对样例 {1, 1, -1, -1}有 f[1][1]1f[2][1]2f[3][1]0f[4][1]3。2状态转移方程 若a[i]1f[i][1]f[i-1][1]1积为 1 的连续子序列个数加 1 f[i][0]f[i-1][0]积继续为 -1若a[i]-1f[i][1]f[i-1][0] f[i][0]f[i-1][1]1最后把所有 f[i][1] 相加就是答案。【算法代码】
#includebits/stdc.h
using namespace std;const int maxn1e65;
int a[maxn];
long long f[maxn][2];
long long ans;int main() {int n;cinn;for(int i1; in; i) cina[i];for(int i1; in; i) {if(a[i]1) {f[i][1]f[i-1][1]1;f[i][0]f[i-1][0];} else if(a[i]-1) {f[i][1]f[i-1][0];f[i][0]f[i-1][1]1;}}for(int i1; in; i) ansansf[i][1];coutansendl;return 0;
}/*
in:
4
1 1 -1 -1out:
6
*/
【参考文献】https://blog.csdn.net/weixin_43914593/article/details/131810636https://blog.csdn.net/hnjzsyjyj/article/details/112797538
