题干：

健健开发了一个游戏叫做<<者护守形隐>>，里面有一个情节是这样的，女主子纯藤武被坏人关在了密室里，作为男主的肖健当然要英雄救美。但是要打开密室的门，必须解开一道谜题。
门上有几个数字围成的一个圈，每次消除一个数字的代价是这个数字旁边的两个数字的gcd，当最后消的只剩两个数时，消除这两个数的代价就是这两个数字的gcd，密室的密码就是消除所有数字的最小代价。
请你帮助肖健解决这个问题
例如数字2,3,4,5，他可以以2的代价(gcd(2,4)==2)消除3，或者以1的代价(gcd(3,5)==1)消除4，或者以1的代价(gcd(3,5)==1)消除2

Input

Input contains multiple test cases. Each test case consists of a single line starting with an integer n which indicates the number of values in the sequence (2 ≤ n ≤ 100). This is followed by n positive integers which make up the sequence of values in the game. All of these integers will be ≤ 1000. Input terminates with a line containing a single 0. There are at most 1000 test cases

Output

For each test case, display the minimum cost of removing all of the numbers

Sample Input 1

4 2 3 4 5
5 14 2 4 6 8
0

Sample Output 1

3
8

题目大意：

一个环状数组，给定可以删去一个数，代价的相邻两个数的gcd，求最小代价。

解题报告：

这题如果不提前把gcd打出来在codeforce上不会T（900ms左右），但是比赛的机子好像就T了。但是这题其实是可以变成环来做的。但是区别就是最后的更新ans不能直接就是让他长度是n的来更新，因为最后剩下的两个点可能在任意的位置，所以我们需要n^2枚举这两个位置，然后分别更新答案，这样得到的才是正解。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 2e5 + 5;
int a[MAX];
int g[1005][1005];
int dp[205][205];
int n;
int main()
{
	for(int i = 0; i<=1000; i++) {
		for(int j = 0; j<=1000; j++) {
			g[i][j] = __gcd(i,j);
		}
	}
	while(~scanf("%d",&n)) {
		if(n == 0) break;
		memset(dp,0x3f,sizeof dp);
		for(int i = 1; i<=n; i++) scanf("%d",a+i),a[i+n] = a[i];
		for(int i = 1; i<=2*n - 1; i++) dp[i][i+1] = 0;//g[a[i]][a[i+1]];
		for(int i = 1; i<=2*n; i++) dp[i][i] = 0;
		for(int len = 3; len<=n; len++) {
			for(int l = 1; l+len-1<=2*n; l++) {
				int r = l+len-1;
				for(int k = l+1; k<r; k++) {
					dp[l][r] = min(dp[l][r] , dp[l][k] + dp[k][r] + g[a[l]][a[r]]);
				}
			}
		}
		int ans = 0x3f3f3f3f;
		for(int i = 1; i<=n; i++) {
			for(int j = i+1; j<=n; j++) {
				ans = min(ans,dp[i][j] + dp[j][i+n] + g[a[i]][a[j]]);
			}
		}
		printf("%d\n",ans);
	}
	return 0 ;
}