#C241017E. [NOI1995] 石子合并

标签（Label）

• 动态规划
• 环

网址（Website）

P1880 [NOI1995] 石子合并 - 洛谷

石子合并 「NOI1995」 - Super

题解（Solution）

主要讲一下化环为链的方法：

对于环，将其倍长，直接当成 $2\times n$ 的序列，最后只需要输出 $f[i][i+n-1]$ 的最优解即可。

详见： AFO 小技巧 | WolfDeer

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 205;
bool ST;

int f[N][N],g[N][N];
int n,a[N],b[N];
int asmn=inf,asmx=-inf;

void Solve(){
	memset(f,0x3f,sizeof f), memset(g,-0x3f,sizeof g);
	
	n = rd();For(i,1,n) a[i]=rd(), b[i]=a[i]+b[i-1];
	For(i,n+1,2*n) a[i]=a[i-n], b[i]=a[i]+b[i-1];
	For(i,1,2*n) f[i][i] = g[i][i] = 0;
	Rof(i,2*n-1,1) For(j,i+1,2*n) For(k,i,j-1) if(i+n-1>=j){
		f[i][j] = min(f[i][j], f[i][k]+f[k+1][j]+b[j]-b[i-1]),
		g[i][j] = max(g[i][j], g[i][k]+g[k+1][j]+b[j]-b[i-1]); 
	}For(i,1,n) asmn = min(asmn, f[i][i+n-1]), asmx = max(asmx, g[i][i+n-1]);
	printf("%lld\n%lld\n",asmn,asmx);
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1, Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}