一道好题
LELElele01
2019-07-16 20:59:05
[环](http://www.gdfzoj.com/oj/contest/570/problems/4)
## 因为有环，所以先开2倍空间，套同区间dp
$$
$$
已经开了2倍空间，可以线性枚举 $,$显然可以用区间dp
## $dp[l][r]$ ##
删除 （$ l $,$ r $） 后最后取$l,r$的最小价值
$$
$$
$dp[i][i+1]$ 为0
$$
$$
```c
for(int len=3;len<=n;len++)
for(l=1; l+len-1<=n;l++)
r=l+len-1
```
$$
$$
$$
$$
```
for(intk=l+1;k<r;k++)
dp[i][j]=min(dp[i][k]+dp[k][r]+gcd(val[l],val[r]))
```
$$
$$
即取走k的价值
$$
$$
套用区间dp模板即可
$$
$$
$$
$$
$$
$$
$$
$$
$dp[l][r]$
使$r-l+1$=n
AC代码：(时间复杂度较高，但数据水，能过)
```c
#include<bits/stdc++.h>
using namespace std;
const int N=110,MAX=1111001;
int n;
int val[N*2];
int dp[N*2][N*2];
int gcd(int x,int y)
{
return x%y==0?y:gcd(y,x%y);
}
int main(){
scanf("%d",&n);
while(n){
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
}
for(int i=1;i<n;i++) val[n+i]=val[i];
for(int i=1;i<=n;i++)dp[i][i+1]=0;
for(int len=3;len<=n;len++){
for(int l=1;l+len-1<2*n;l++){
int r=l+len-1;
dp[l][r]=MAX;
for(int k=l+1;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+gcd(val[l],val[r]));
}
}
}
int ans=MAX;
for(int l=1;l<n;l++){
for(int j=l+1;j<=n;j++){
ans=min(ans,dp[l][j]+dp[j][l+n]+gcd(val[l],val[j]));
}
}
printf("%d\n",ans);
scanf("%d",&n);
}
}
```
正解
```c
#include<bits/stdc++.h>
using namespace std;
const int N=110,MAX=1111001;
int n;
int val[N*2];
int dp[N*2][N*2],g[N*2][N*2];
int gcd(int x,int y)
{
return x%y==0?y:gcd(y,x%y);
}
int main(){
scanf("%d",&n);
while(n){
for(int i=1;i<=n;i++){
scanf("%d",&val[i]);
}
for(int i=1;i<=n;i++) val[n+i]=val[i];
for(int l=1;l<2*n;l++)
for(int r=l+1;r<=2*n;r++){
//printf("r:%d",l);puts("check");
g[l][r]=gcd(val[l],val[r]);
//g[r][l]=g[l][r];
}
for(int i=1;i<=n;i++)dp[i][i+1]=0;
for(int len=3;len<=n;len++){
for(int l=1;l+len-1<2*n;l++){
int r=l+len-1;
dp[l][r]=MAX;
int gd=g[l][r];
for(int k=l+1;k<r;k++){
dp[l][r]=min(dp[l][r],dp[l][k]+dp[k][r]+gd);
}
}
}
int ans=MAX;
for(int l=1;l<n;l++){
for(int j=l+1;j<=n;j++){
int gd=g[l][j];
ans=min(ans,dp[l][j]+dp[j][l+n]+gd);//非常重要
}
}
printf("%d\n",ans);
scanf("%d",&n);
}
}
```
## 只剩3个数的时候一定要再比一次！！！
因为前面对$len$的处理，默认$dp[l][l+n]$ 会最后取$l,l+n,$
$$
$$
假设最后3个数为$l,j,l+n$
$$
可能先取l+n或l更优