高爆999广告,骷髅打金服,爆率+9999999999

高爆999广告

题意

跟弱化版差不多，只不过石头变成了环状，输出加上了最大

思路

先把弱化版的代码复制过来

解决环状：把长度乘 2，就能把每种情况遍历出来^[1]

解决最大：把最小的代码复制一下，改成 max 就行了

注意：最后要把每种情况遍历一遍找最大和最小（33:36）

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 405,INF = 0x3fffffff;
int a[N],fmn[N][N],b[N],fmx[N][N],mx,mn = INF;
int main(int argc, char **argv){
	for (int i = 0;i < N;i++)	fill(fmn[i],fmn[i] + N,INF);
	int n;
	cin >> n;
	for (int i = 1;i <= n;i++){
		cin >> a[i];
		a[i + n] = a[i];	// 由于是环状，所以把长度乘 2 来解决问题
		// 一堆时没有代价
		fmn[i][i] = 0;
		fmn[i + n][i + n] = 0;
		fmx[i][i] = 0;			// fmx 这两行可以省，因为本来就是 0
		fmx[i + n][i + n] = 0;
	}
	for (int i = 1;i <= 2 * n;i++){
		b[i] = b[i - 1] + a[i];
	}
	for(int len = 2;len <= 2 * n;len++){
		for (int i = 1;i <= 2 * n - len + 1;i++){
			int j = i + len - 1;
			for (int k = i;k < j;k++){
				fmn[i][j] = min(fmn[i][j],fmn[i][k] + fmn[k + 1][j]);
				fmx[i][j] = max(fmx[i][j],fmx[i][k] + fmx[k + 1][j]);
			}
			// 累计代价
			fmn[i][j] += b[j] - b[i - 1];
			fmx[i][j] += b[j] - b[i - 1];
		}
	}
	for (int i = 1;i <= n;i++){	// 由于是环形，所以每一段都要比较
		mx = max(mx,fmx[i][i + n - 1]);
		mn = min(mn,fmn[i][i + n - 1]);
	}
	printf("%d\n%d",mn,mx);
	return 0;
}