题目 题意：求任意连续区间负数，0，正数的个数 错因：暴力超时（1000ms跑3e8） 思路：用DP dp[i][0]:以i为截止位置时负数的个数； dp[i][1]:以i为截止位置时零的个数； dp[i][2]:以i为截止位置时正数数的个数； AC代码
#include<bits/stdc++.h> using namespace std; int a[200005], b[200005], c[200005], x[200005]; long long sum1, sum2, sum3; int main() { int n, i; sum1=sum2=sum3=0; scanf("%d", &n); memset(a, 0, sizeof(a)); memset(b, 0, sizeof(b)); memset(c, 0, sizeof(c)); for(i=0; i<n; i++) { scanf("%d", &x[i]); if(i==0) { if(x[i]==0) b[i]++; else if(x[i]>0) c[i]++; else a[i]++; } else { if(x[i]>0) { c[i]=c[i-1]+1; a[i] = a[i-1]; b[i] = b[i-1]; } else if(x[i]==0) { c[i]=0; a[i]=0; b[i]=a[i-1]+c[i-1]+b[i-1]+1; } else if(x[i]<0) { c[i]=a[i-1]; a[i]=c[i-1]+1; b[i]=b[i-1]; } } } for(i=0; i<n; i++) { sum1+=a[i]; sum2+=b[i]; sum3+=c[i]; } printf("%lld %lld %lld\n", sum1, sum2, sum3); return 0; }