題目連結
只要大於0就直接拆開,這就是貪心演算法
解題核心
本次用到貪心演算法
如果右邊的值>0,那麼他乘以越高位值(將陣列拆成越多塊)得出的值也越大
相反,如果最左邊的值<0,那麼就將其跟次位相加至>0就可以開始
因為用乘的會RE,所以用加法的(原理相同)
a*3==a+a+a
利用這個原理==>只要從陣列後面加入且值大於>0就加入ans等同於1(加第二次就是2)
可以舉下列例子:
1 2 3 -4 5
利用貪心
第一筆:5>0 ==>放入ans(目前:5)
第二筆:5+(-4)=1>0 ==>放入ans(5+1)
第三筆:1+3=4>0 ==>放入ans(4+6)
第四筆:4+2=6>0 ==>放入ans(10+6)
第五筆:6+1=7>0 ==>放入ans(16+7=23)
就等同於:
1(加一次)+2(加兩次)*2+3(加三次)*3-4(加四次)*4+5(加五次)*5
1+2 *2 + 3*3- 4* 4+5*5=23
```cpp
#include <iostream>
#include <vector>
#define ll long long int
#define dasabi uint
using namespace std;
/*
//* 題目:Theofanis' Nightmare
題目連結:https://codeforces.com/contest/1903/problem/C
解題者:神里綾華的狗(dasabi7414)
使用語言:C++11
本次技巧:Greedy
解題連結:https://github.com/archie0732/c-solution/blob/main/codeforce/Theofanis'%20Nightmare.md
本文會放在IT幫忙
//* 備註:本題是使用"貪心演算法"請先確保已經熟悉!!
*/
int main(int argc, char const *argv[])
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++)
cin >> v[i];
// 這裡一定要用long long(因為我被搞過XD)
ll sum = 0;
ll ans = 0;
// 倒著回來加
for (int i = n - 1; i >= 0; i--)
{
// 如果相加大於0==>加入解答,反之==>繼續加(至其倒陣列坐左邊或sum>0)
sum = v[i] + sum;
if (sum > 0 || i == 0)
{
ans += sum;
}
}
cout << ans << endl;
}
return 0;
}
// 總之,要先熟悉貪心演算法(Greedy),與多點的練習。
// 用乘法可會一直RE是正常的嗎