G Gaming with Mia
思路：我們能找出某些情況：
-1 1 -1
-1 1 1 -1
-1 1 1 1 -1
-1 1 ... 1 -1
我們發現如果大于5個數相乘，則它一定可以分解成其他更優的情況相乘再相加，（當然如果出現0，也可以最極限情況5個數相乘）
時間復雜度就是：O（1e6*10*5）
那么我們就可以進行dp，例如：
dp[5] = dp[4] + a[5];
dp[5] = dp[3] + a[5] * a[4];
dp[5] = dp[2] + a[5] * a[4] * a[3];
dp[5] = dp[1] + a[5] * a[4] * a[3] * a[2];
dp[5] = dp[0] + a[5] * a[4] * a[3] * a[2] * a[1]，
總共五種情況，然后取max，
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 6 using namespace std; 7 8 #define ll long long 9 10 const int INF = 1e9; 11 12 void solve(){ 13 14 int T; 15 scanf("%d", &T); 16 while(T--){ 17 int n; 18 scanf("%d", &n); 19 20 vector<int > a(n + 10); 21 vector<int > dp(n + 10, -INF); 22 for(int i = 1; i <= n; ++i) scanf("%d", &a[i]); 23 dp[0] = 0; 24 for(int i = 1; i <= n; ++i){ 25 int x = 1; 26 for(int j = 1; j <= 5; ++j){ 27 if(i - j < 0) continue; 28 x *= a[i - j + 1]; 29 dp[i] = max(dp[i], dp[i - j] + x); 30 } 31 } 32 //printf("ans = %d\n", dp[n]); 33 printf("%d\n", dp[n]); 34 } 35 } 36 37 int main(){ 38 39 solve(); 40 41 return 0; 42 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/45334.html
標籤：其他
上一篇：淺談微前端在滴滴車服中的應用實踐
下一篇：樹和森林