【玲珑杯R7 D】Pick Up Coins

客官°小女子只卖身不卖艺 2021-10-26 17:16 350阅读 0赞

Time Limit：10s Memory Limit：1024MByte

Submissions：335Solved：126

DESCRIPTION  
There are n coins in a line, indexed from 0 to n-1. Each coin has its own value.You are asked to pick up all the coins to get maximum value. If the you pick coini (1 ≤ i ≤n-2), you will get  
v  
a  
l  
u  
e  
\[  
l  
e  
f  
t  
\]  
×  
v  
a  
l  
u  
e  
\[  
i  
\]  
×  
v  
a  
l  
u  
e  
\[  
r  
i  
g  
h  
t  
\]  
value\[left\]×value\[i\]×value\[right\] coin value. Here left and right are adjacent indices of i. After the picked, the left and right then becomes adjacent.

Note.

If you pick the first coin, you can assume the value\[left\] is 1.

If you pick the last coin, you can assume the value\[right\] is 1.

Find the maximum value when you pick up all the coins.

INPUT  
The first line is a single integer  
T  
T, indicating the number of test cases.

For each test case:

The first line contains a number  
n  
n (3≤  
n  
n ≤103) — The number of magic coins.

The second line contains  
n  
n numbers ( all numbers ≤10) — The value of each coin.  
OUTPUT  
For each test case, return a number indicates the maximum value after you picked up all the coins.  
SAMPLE INPUT  
1  
3  
3 5 8  
SAMPLE OUTPUT  
152  
HINT  
Hint  
In the sample,  
answer = 120 + 24 + 8 = 152  
\[3,5,8\] –> \[3,8\] –> \[8\]

【题目链接】:[http://www.ifrog.cc/acm/problem/1074][http_www.ifrog.cc_acm_problem_1074]

【题解】  
  
设f\[i\]\[j\]表示i到j这个区间里面的硬币都被拿掉了能够获得的最大值是多少;  
转移方法如下;  
枚举中间的断点吧.

int solve(int l,int r)
    {
        if (f[l][r]!= (-INF))
            return f[l][r];
        if (l>r)
            return 0;
        if (l==r)
            return a[l-1]*a[l]*a[r+1];
        int ma = -INF;
        rep1(k,l,r)//0 1 2
            ma = max(ma,solve(l,k-1)+solve(k+1,r)+a[l-1]*a[k]*a[r+1]);
        return f[l][r] = ma;
    }

【完整代码】

#include <bits/stdc++.h>
    using namespace std;
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define LL long long
    #define rep1(i,a,b) for (int i = a;i <= b;i++)
    #define rep2(i,a,b) for (int i = a;i >= b;i--)
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    #define rei(x) scanf("%d",&x)
    #define rel(x) scanf("%I64d",&x)
    
    typedef pair<int,int> pii;
    typedef pair<LL,LL> pll;
    
    const int MAXN = 1e3+10;
    const int INF = 0x3f3f3f3f;
    const int dx[9] = {
         0,1,-1,0,0,-1,-1,1,1};
    const int dy[9] = {
         0,0,0,-1,1,-1,1,-1,1};
    const double pi = acos(-1.0);
    
    int f[MAXN][MAXN],n,a[MAXN];
    bool bo[MAXN][MAXN];
    
    int solve(int l,int r)
    {
        if (f[l][r]!= (-INF))
            return f[l][r];
        if (l>r)
            return 0;
        if (l==r)
            return a[l-1]*a[l]*a[r+1];
        int ma = -INF;
        rep1(k,l,r)//0 1 2
            ma = max(ma,solve(l,k-1)+solve(k+1,r)+a[l-1]*a[k]*a[r+1]);
        return f[l][r] = ma;
    }
    
    int main()
    {
        //freopen("F:\\rush.txt","r",stdin);
        int T;
        rei(T);
        while (T--)
        {
            rep1(i,0,1001)
                rep1(j,0,1001)
                    f[i][j] = -INF;
            rei(n);
            a[0] = a[n+1] = 1;
            rep1(i,1,n)
                rei(a[i]);
            printf("%d\n",solve(1,n));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/AWCXV/p/7626773.html

[http_www.ifrog.cc_acm_problem_1074]: http://www.ifrog.cc/acm/problem/1074