B. Chocolates
cf题目地址：https://codeforces.com/problemset/problem/1139/B
You went to the store, selling n types of chocolates. There are ai chocolates of type i in stock.
You have unlimited amount of cash (so you are not restricted by any prices) and want to buy as many chocolates as possible. However if you buy xi chocolates of type i (clearly, 0≤xi≤ai), then for all 1≤j<i at least one of the following must hold:
xj=0 (you bought zero chocolates of type j)
xj<xi (you bought less chocolates of type j than of type i)
For example, the array x=[0,0,1,2,10] satisfies the requirement above (assuming that all ai≥xi), while arrays x=[0,1,0], x=[5,5] and x=[3,2] don’t.
Calculate the maximum number of chocolates you can buy.
Input
The first line contains an integer n (1≤n≤2⋅105), denoting the number of types of chocolate.
The next line contains n integers ai (1≤ai≤109), denoting the number of chocolates of each type.
Output
Print the maximum number of chocolates you can buy.
Note
In the first example, it is optimal to buy: 0+0+1+3+6 chocolates.
In the second example, it is optimal to buy: 1+2+3+4+10 chocolates.
In the third example, it is optimal to buy: 0+0+0+1 chocolates.
题意： 后面的数比前面大可以加入总和，前面的数尽量大。
基本用下有道云和看下note和Examples就可以懂意思。
从前面加到后面要注意的东西太多了。
/***
* ,[email protected]@&
* :9H####@@@@@Xi
* [email protected]@@@@@@@@@@@@@8
* ,[email protected]@@@@@@@@[email protected]@@@@@8
* :[email protected]@@@X3hi8Bs;[email protected]@@@@Ah,
* ,8i [email protected]@@B: 1S ,[email protected]@@@@@#8;
* 1AB35.i: [email protected]@8 . SGhr ,[email protected]@@@@@@@S
* [email protected] 18Hhh3i .i3r ,[email protected]@@@@@@@@5
* ;@&i,58r5 rGSS: :[email protected]@@@@@@@@@A
* 1#i . 9i hX. .: [email protected]@@@@@@@@@@1
* sG1, ,G53s. 9#Xi;hS5 [email protected]@@@@@@B1
* .h8h.,[email protected]@@MXSs, #@H1: [email protected]
* s ,@@@@@@@@@@@@Xhi, r#@@X1s9M8 .GA981
* ,. rS8H#@@@@@@@@@@#HG51;. .h31i;[email protected] [email protected]@@@BS;i;
* [email protected]@@@@@@@@@@@@@#MHXG893hrX#[email protected]@@@@@@@@@MS
* [email protected]@[email protected]@@hsX#@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@&,
* :[email protected]#[email protected]@Brs ,[email protected]@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@B,
* [email protected]@@#@@#MX 51 r;[email protected]@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@8
* :[email protected]@@@@@@@@@@&[email protected] :Gs .;[email protected]@@@@@@@@@@@@@@@@@@@@@@@@@@@@@:
* s&HA#@@@@@@@@@@@@@@M89A;.8S. ,[email protected]@@@@@@@@@@@@@@@@@@@@@@@@@@r
* ,[email protected]@@@@@@@@@@@@@@@@@@5 5B3 ;. ;@@@@@@@@@@@@@@@@@@@@@@@@@@@i
* 5#@@#&@@@@@@@@@@@@@@@@@@9 .39: ;@@@@@@@@@@@@@@@@@@@@@@@@@@@;
* [email protected]@@X:[email protected]@@@@@@@@@@@@@@#; ;31. [email protected]@@@@@@@@@@@@@@@@@@@@@@@@@:
* SH#@[email protected]@@@@@@@@@@@@B :. [email protected]@@@@@@@@@@@@@@@@@@@@@@@@@5
* ,:. [email protected]@@@@@@@@@@#HB5 [email protected]@@@@@@@@@@@@@@@@@@@@@@@@B
* ,[email protected]&1;i19911i,. [email protected]@@@@@@@@@@@@@@@@@@@@@@@@@S
* ,,,rHAri1h1rh&@#353Sh: [email protected]@@@@@@@@@@@@@@@@@@@@@@@@#:
* [email protected]#5S553&@@#h i:i9S #@@@@@@@@@@@@@@@@@@@@@@@@@A.
*
*
* 又有bug，你妹妹呀！
*/
所以从后面加到前面就容易多了！！
ac代码
#include<iostream>
using namespace std;
int main()
{
long long int i, n, sum;
long long int a[200100] = { 0 };
cin >> n;
sum = 0;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = n; i > 0; i--)
{
if (a[i - 1] >= a[i])
a[i - 1] = a[i] - 1;
if (a[i] == 0)
break;
sum = sum + a[i];
}
cout << sum << endl;
//system("pause");
return 0;
}