https://www.luogu.com.cn/problem/P1063

枚举区间的时候，tail 数组也要枚举…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int MAX=100+10;
int n,a[MAX*2],d[MAX*2][MAX*2];
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,0,n){
		sf(a[i]);
		a[i+n]=a[i];
	}
	a[n*2]=a[0];
	fi(k,2,n+1)
		fi(i,0,n*2-k){ //!!
			int j=i+k-1;
			fi(h,i,j){
				d[i][j]=max(d[i][j],d[i][h] + d[h+1][j] + a[i]*a[h+1]*a[j+1]);
			}
		}
	int _max=0;
	fi(i,0,n){
		_max=max(_max,d[i][i+n-1]);
	}
	pf(_max);
	return 0;
}