首页 > 代码库 > 四边形不等式(石子合并)
四边形不等式(石子合并)
动态规区间dp做这道题的话应该是n^3,下面的代码优化到了n^2,用四边形不等式优化。
设mid[i][j]是dp[i][j]的最优解的断点,即它左区间的右端点,那么mid[i][j-1]<=mid[i][j]<=mid[i+1][j],所以在求解dp[i][j]时,枚举k可以只枚举这两个值之间枚举就好,
程序要先枚举区间长度,在枚举左端点,枚举每个区间长度时,他们的k总是只从1到n,只走一遍,所以这就相当于优化了一层,变成了O(n2)的。
比如len长度为3时,dp[1][3]只会枚举mid[1][2]-mid[2][3],如上。然后dp[2][4]时,枚举mid[2][3]-mid[3][4]。以此类推。
1 #include<cstdio> 2 #include<algorithm> 3 using namespace std; 4 const int MAXN = 4010; 5 const int INF = 1e8; 6 int dp[MAXN][MAXN],a[MAXN],sum[MAXN],mid[MAXN][MAXN],n; 7 8 int main() 9 {10 scanf("%d",&n);11 for (int i=1; i<=n; ++i)12 scanf("%d",&a[i]), sum[i] = sum[i-1]+a[i];13 14 for (int i=1; i<=n; ++i)15 dp[i][i] = 0, mid[i][i] = i;16 17 for (int len=1; len<n; ++len)//求右端点(i+len-1)会减1,先在这减了 18 {19 for (int i=1; i<=n-len; ++i)//左端点i最大值是右端点等于n时,(i+len)=n,i=n-len 20 {21 int j = i+len;//右端点 22 dp[i][j] = INF;23 for (int k=mid[i][j-1]; k<=mid[i+1][j]; ++k) 24 {25 if (dp[i][j]>dp[i][k]+dp[k+1][j])26 {27 dp[i][j] = dp[i][k]+dp[k+1][j];28 mid[i][j] = k;29 }30 }31 dp[i][j] += sum[j]-sum[i-1];32 }33 }34 printf("%d",dp[1][n]);35 return 0;36 }
四边形不等式(石子合并)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。