【TYVJ 1056】能量项链

时间：2024-01-20 20:07:27

【题目链接】传送门

【题解大意】

这题好水，可我还是调了一会，以下为调试中出现过的错误：

1.更新取值时弄清楚区间范围是[l,k][k+1,r]还是[l,k][k,r]

2.对于环形处理时左端点的取值最大可以到达(n<<1)要记住

3.每题的枚举k具体的起止到底是[l,r]还是[l+1,r]还是[l+1,r-1]...要根据题目的理解各异

【code】

#include<bits/stdc++.h>

using namespace std;

#define File ""

#define ll long long

#define ull unsigned long long

#define rep(k,i,j) for(int k = i;k <= j; ++k)

#define FOR(k,i,j) for(int k = i;k >= j; --k)

inline void file(){

    freopen(File".in","r",stdin);

    freopen(File".out","w",stdout);

}

inline int read(){

    int x=,f=;   char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-; ch=getchar();}

    while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-''; ch=getchar();}

    return x*f;

}

const int mxn = ;

int n;

int a[mxn<<],f[mxn<<][mxn<<];

int main(){

//    file();

    n = read();

    rep(i,,n) a[n+i] = a[i] = read();

    memset(f,,sizeof f);

    rep(i,,n<<) f[i][i] = a[i];

    rep(len,,n+){

        rep(l,,(n<<)-len+){

            int r = l+len-;

            rep(k,l+,r-)

                f[l][r] = max(f[l][r],f[l][k]+f[k][r]+a[l]*a[k]*a[r]);

        }

    }

//    rep(i,1,n) printf("%d\n",f[i][i+n]);

//    puts("");

    int ans = ;

    rep(i,,n) ans = max(ans,f[i][i+n]);

    printf("%d\n",ans);

    return ;

}

/*

4

2 3 5 10

*/

相关文章