tle了我几个月.......谢谢cqf大牛的算法。 //State: 0.22s 1512kb //用l,r两个数组保存当前元素向左向右访问能够达到的最大下标，因此可用dp //另：此题甚bt，数据量大的惊人，而且有陷阱，必须用scanf。我用cin的时候起码读了10s......... #include <cstdio> int a[100000], l[100000], r[100000], n; int main(){ freopen("in.txt", "r", stdin); while(scanf("%d", &n) && n) {  int i;  double max = 0.00;  for(i = 0; i < n; i ++)  {   scanf("%d", &a[i]);       }  for(i = 0; i < n; i ++)  {   l[i] = i;   while(l[i] > 0 && a[i] <= a[l[i] - 1])   {    l[i] = l[l[i] - 1];   }     }  //pl();  for(i = n - 1; i >= 0; i --)  {   r[i] = i;   while(r[i] < n - 1 && a[i] <= a[r[i] + 1])   {    r[i] = r[r[i] + 1];   }   double t = double((r[i] - l[i] + 1) * double(a[i]));   if(max < t)    max = t;  }  //pr();  printf("%0.0f\n", max); } return 0;}

评论