惊恐地发现自己连区间 DP 都会错 2333
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- #include <cmath>
- #define R(a,b,c) for(register int a = (b); a <= (c); ++ a)
- #define nR(a,b,c) for(register int a = (b); a>= (c); -- a)
- #define Max(a,b) ((a)> (b) ? (a) : (b))
- #define Min(a,b) ((a) <(b) ? (a) : (b))
- #define Fill(a,b) memset(a, b, sizeof(a))
- #define Abs(a) ((a) < 0 ? -(a) : (a))
- #define Swap(a,b) a^=b^=a^=b
- #define ll long long
- #define ON_DEBUG
- #ifdef ON_DEBUG
- #define D_e_Line printf("\n\n----------\n\n")
- #define D_e(x) cout << #x << "=" << x << endl
- #define Pause() system("pause")
- #define FileOpen() freopen("in.txt","r",stdin);
- #else
- #define D_e_Line ;
- #define D_e(x) ;
- #define Pause() ;
- #define FileOpen() ;
- #endif
- struct iOS{
- template<typename ATP>iOS& operator>> (ATP &x){
- x = 0; int f = 1; char c;
- for(c = getchar(); c <'0' || c> '9'; c = getchar()) if(c == '-') f = -1;
- while(c>= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
- x*= f;
- return *this;
- }
- }io;
- using namespace std;
- const int N = 1007;
- int a[N], f[N][N];
- int main(){
- //FileOpen();
- int n;
- io>> n;
- R(i,1,n){
- io>> a[i];
- a[i + n] = a[i];
- }
- int ans = 0;
- R(len,2,n){
- R(l,1,n <<1){
- int r = l + len - 1;
- if(r> (n << 1)) continue;
- R(k, l + 1, r){
- f[l][r] = Max(f[l][r], f[l][k - 1] + f[k][r] + a[l] * a[k] * a[r + 1]);
- ans = Max(ans, f[l][r]);
- //1 printf("f %d %d :%d\n", l, r, f[l][r]);
- }
- }
- }
- printf("%d", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3131350.html