蓝桥杯算法提高VIP-合并石子

题目 题解

区间dp

我是枚举的两个边界，但是出现问题了，左边界的枚举必须要从后向前。 因为需要先获取区间长度小的对应的dp，才能递推出大区间的dp值；如果我左区间从左向右遍历，第二层右边界也从左向右遍历，则会先遍历到大区间，而与之相关的小区间值还未计算出来，导致错误。 这时就需要从右向左遍历左边界，保证每次计算的大区间所需的小区间值都已经算出来了。

这道题需要四边形不等优化才能完全AC，但为了蓝桥杯国奖，没必要。

代码

#include
using namespace std;
const int N = 1e3+10;

int dp[N][N], sum[N+N], n, s;


int main()
{
	memset(dp, 0x3f, sizeof dp);
	cin>>n;
	for(int i = 1;i >s, sum[i] = sum[i-1] + s, dp[i][i] = 0;
	
	for(int i = n-1;i >= 1;i --) {
		for(int j = i+1;j