http://ac.jobdu.com/problem.php?pid=1550
默认给最少“1”， 如果a[i] > a[i-1], 比前面多给一个。如果 a[i] < a[i-1], a[i] 给“1”个，检查a[i]前面的序列 如果不满足条件的就多给糖果
参考了http://blog.csdn.net/xiexingshishu/article/details/20319825
#include <cstdio> #include <algorithm> using namespace std; #define rep(i,j,k) for(int i=j;i<=k;i++) #define per(i,j,k) for(int i=k;i>=j;i--) #define inone(i) scanf("%d",&i) const int maxn = 1e5 + 10; int a[maxn], n, r, cnt, t[maxn]; int main() { while (inone(n) != EOF) { cnt = 0; rep(i, 0, n - 1) { inone(a[i]); t[i] = 1; if (i == 0) continue; if (a[i - 1] < a[i]) t[i] = t[i - 1] + 1; else if (a[i - 1] > a[i]) { for (int j = i - 1; j >= 0 && a[j] > a[j + 1]; j--) t[j] = max(t[j],t[j + 1] + 1); } } rep(i, 0, n - 1) cnt += t[i]; printf("%d\n",cnt); } return 0; }
