Advertisement
Josif_tepe

Untitled

Apr 11th, 2023
561
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.97 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <cstring>
  4. #include <map>
  5. using namespace std;
  6. typedef long long ll;
  7. const int maxn = 505;
  8. ll potions[maxn];
  9. ll dp[maxn][maxn];
  10. ll sum(int i, int j) {
  11.     ll result = 0;
  12.     for(int k = i; k <= j; k++) {
  13.         result += potions[k];
  14.     }
  15.     return result % 100;
  16. }
  17. ll rec(int i, int j) {
  18.     if(i + 1 == j) {
  19.         return potions[i] * potions[j];
  20.     }
  21.     if(i >= j) {
  22.         return 0;
  23.     }
  24.     if(dp[i][j] != -1) {
  25.         return dp[i][j];
  26.     }
  27.     ll result = 2e15;
  28.     for(int k = i; k < j; k++) {
  29.         result = min(result, rec(i, k) + rec(k + 1, j) + sum(i, k) * sum(k + 1, j));
  30.     }
  31.     return dp[i][j] = result;
  32. }
  33. int main() {
  34.     ios_base::sync_with_stdio(false);
  35.     int n;
  36.     while(cin >> n) {
  37.        
  38.         for(int i = 0; i < n; i++) {
  39.             cin >> potions[i];
  40.         }
  41.         memset(dp, -1, sizeof dp);
  42.         cout << rec(0, n - 1) << endl;
  43.     }
  44.     return 0;
  45. }
  46.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement