本文主要是介绍【2016-2017 ACM-ICPC (ECNA 2016) F】Removal Game(区间dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/gym/101196
题目大意：有n个数字成环，删掉一个数字的代价是周围俩数的gcd，只剩俩数字的时候用这俩数字的gcd作为代价，问删掉所有数字的最小代价
题目思路：考虑区间dp，dp[i][j]表示i，j区间内，删的只剩下i和j的最小代价，当长度为1和2时，dp值为0，其他时候枚举中间的点作为最后一个被删除的点，那么dp[i][j]就是dp[i][k]+dp[k][j]+gcd(a[i],a[j]),最后枚举最后被删除的两个点即可
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define inf 0x3f3f3f3f
const int MAXN = 1005;
int n,a[MAXN],dp[MAXN][MAXN];
int main()
{while(~scanf("%d",&n)&&n){rep(i,1,n)scanf("%d",&a[i]),a[i+n]=a[i];memset(dp,0x3f,sizeof(dp));rep(i,1,n){rep(j,1,2*n){int x=j,y=j+i-1;if(y>2*n)break;if(x==y||x+1==y)dp[x][y]=0;else{rep(k,x+1,y-1)dp[x][y]=min(dp[x][y],dp[x][k]+dp[k][y]+__gcd(a[x],a[y]));}}}int ans=inf;rep(i,1,n){rep(j,i+1,i+n-1){ans=min(ans,dp[i][j]+dp[j][i+n]+__gcd(a[i],a[j]));}}printf("%d\n",ans);}return 0;
}
这篇关于【2016-2017 ACM-ICPC (ECNA 2016) F】Removal Game(区间dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
