Wine Shelf
You have a collection of NN wines placed next to each other on a shelf. Let's number the wines from left to right as they are standing on the shelf with integers from 1 to N, respectively. The price of the ithith wine is PiPi (prices of different wines can be different).
Because the wines get better every year, supposing today is the year 1, on year YY the price of the ithith wine will be Y∗PiY∗Pi, that is YY times the value of wine that current year.
You want to sell all the wines you have, but you want to sell exactly one wine per year, starting this year. One more constraint - each year you are allowed to sell only either the leftmost or the rightmost wine on the shelf and you are not allowed to reorder the wines on the shelf (i.e. they must stay in the same order as they are in the beginning).
You want to find out, what is the maximum profit you can get, if you sell the wines in optimal order. Since profit can be really large, report profit modulo 109+7109+7.
1≤N≤8001≤N≤800
1≤Pi≤8001≤Pi≤800
INPUT
The first line contains a single integer NN - number of wine bottles on the shelf.
The next line contains NN space separated integers PiPi, for 1≤i≤N1≤i≤N.
OUTPUT
Output a single integer - maximum profit you can make selling wines in some order modulo 109+7109+7.
EXAMPLE
Sample 1 INPUT:
properties
4 1 4 2 3
Sample 1 OUTPUT:
text
29
#include <bits/stdc++.h>using namespace std;#define int long long int#define F first#define S second#define pb push_back#define si set <int>#define vi vector <int>#define pii pair <int, int>#define vpi vector <pii>#define vpp vector <pair<int, pii>>#define mii map <int, int>#define mpi map <pii, int>#define spi set <pii>#define endl "\n"#define sz(x) ((int) x.size())#define all(p) p.begin(), p.end()#define double long double#define que_max priority_queue <int>#define que_min priority_queue <int, vi, greater<int>>#define bug(...) __f (#__VA_ARGS__, __VA_ARGS__)#define print(a) for(auto x : a) cout << x << " "; cout << endl#define print1(a) for(auto x : a) cout << x.F << " " << x.S << endl#define print2(a,x,y) for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endlinline int power(int a, int b){int x = 1;while (b){if (b & 1) x *= a;a *= a;b >>= 1;}return x;}template <typename Arg1>void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }template <typename Arg1, typename... Args>void __f (const char* names, Arg1&& arg1, Args&&... args){const char* comma = strchr (names + 1, ',');cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);}const int N = 1e9+7;int dp[800][800];int helper(int l,int r,vector<int>&v,int year){if(l>r)return 0;if(dp[l][r]!=0)return dp[l][r];dp[l][r]=max((year*v[l]+helper(l+1,r,v,year+1))%N,(year*v[r]+helper(l,r-1,v,year+1))%N);// cout<<dp[l][r]<<endl;return dp[l][r];}void solve() {int n;cin>>n;vi v(n);for (int i = 0; i < n; i++){cin>>v[i];}cout<<helper(0,n-1,v,1)%N;}int32_t main(){ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);clock_t z = clock();int t = 1;// cin >> t;while (t--) solve();return 0;}
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.