洛谷P1880 [NOI1995]石子合并

叁歲伎倆 2022-05-26 23:06 171阅读 0赞

![70][]

思路：

将数后面复制一份

dp【i】【j】=max（dp【i】【j】，dp【i】【k】+dp【k+1】【j】+sum【j】-sum【i-1】

i<=k<j

写法一：记忆化搜索

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define Maxn 210
    #define INF 0x7fffffff
    int sum[Maxn];
    int Fmin[Maxn][Maxn];
    int Fmax[Maxn][Maxn];
    int N;
    
    int searchMax(int l,int r)
    {
    	if (Fmax[l][r]) return Fmax[l][r];
    	else if (l == r)  return Fmax[l][r] = 0;
    	int tmp = 0;
    	for (int k = l; k < r; k++)
    		tmp = max(tmp, searchMax(l, k) + searchMax(k + 1, r) + sum[r] - sum[l - 1]);
    	return Fmax[l][r] = tmp;
    }
    
    
    int searchMin(int l, int r)
    {
    	if (Fmin[l][r]) return Fmin[l][r];
    	else if (l == r)  return Fmin[l][r] = 0;
    	int tmp = INF;
    	for (int k = l; k < r; k++)
    		tmp = min(tmp, searchMin(l, k) + searchMin(k + 1, r) + sum[r] - sum[l - 1]);
    	return Fmin[l][r] = tmp;
    }
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    	cin >> N;
    	for (int i = 1; i <= N; i++)
    	{
    		cin >> sum[i];
    		sum[i + N] = sum[i];
    	}
    
    	for (int i = 1; i <= 2 * N; i++)
    		sum[i] += sum[i - 1];
    
    	searchMax(1, 2 * N);
    	searchMin(1, 2 * N);
    
    	int ans_max = 0;
    	int ans_min = INF;
    	for (int i = 1; i <= N; i++)
    	{
    		ans_max = max(ans_max, Fmax[i][N+i-1]);
    		ans_min = min(ans_min, Fmin[i][N + i - 1]);
    	}
    
    	cout << ans_min << '\n' << ans_max;
    	return 0;
    }

写法二：四边形不等式优化

在这里，s【i-1】【j】<=k<=s【i】【j+1】

## 1介绍及证明 ##

[编辑][Link 1]

四边形不等式是一种比较常见的优化动态规划的方法：

设m\[i,j\]表示动态规划的[状态量][Link 2]。

m\[i,j\]有类似如下的[状态转移方程][Link 3]：

m\[i,j\]=opt\{m\[i,k\]+m\[k,j\]\}(i≤k≤j)

如果对于任意的a≤b≤c≤d，有m\[a,c\]+m\[b,d\]≤m\[a,d\]+m\[b,c\]，那么m\[i,j\]满足四边形不等式。

以上是适用这种优化方法的必要条件

对于一道具体的题目，我们首先要证明它满足这个条件，一般来说用[数学归纳法][Link 4]证明，根据题目的不同而不同。

通常的动态规划的复杂度是O(n^3)，我们可以优化到O(n^2)

设s\[i,j\]为m\[i,j\]的决策量，即m\[i,j\]=m\[i,s\[i,j\]\]+m\[s\[i,j\],j\]

我们可以证明，s\[i,j-1\]≤s\[i,j\]≤s\[i+1,j\] （证明过程见下）

那么改变状态转移方程为：

m\[i,j\]=opt\{m\[i,k\]+m\[k,j\]\}(s\[i,j-1\]≤k≤s\[i+1,j\])

复杂度分析：不难看出，复杂度决定于s的值，以求m\[i,i+L\]为例，

(s\[2,L+1\]-s\[1,L\])+(s\[3,L+2\]-s\[2,L+1\])…+(s\[n-L+1,n\]-s\[n-L,n-1\])=s\[n-L+1,n\]-s\[1,L\]≤n

所以总复杂度是O(n)

对s\[i,j-1\]≤s\[i,j\]≤s\[i+1,j\]的证明：

设mk\[i,j\]=m\[i,k\]+m\[k,j\]，s\[i,j\]=d

对于任意k<d，有mk\[i,j\]≥md\[i,j\]（这里以m\[i,j\]=min\{m\[i,k\]+m\[k,j\]\}为例,max的类似），接下来只要证明mk\[i+1,j\]≥md\[i+1,j\]，那么只有当s\[i+1,j\]≥s\[i,j\]时才有可能有ms\[i+1,j\]\[i+1,j\]≤md\[i+1,j\]

(mk\[i+1,j\]-md\[i+1,j\])-(mk\[i,j\]-md\[i,j\])

=(mk\[i+1,j\]+md\[i,j\])-(md\[i+1,j\]+mk\[i,j\])

=(m\[i+1,k\]+m\[k,j\]+m\[i,d\]+m\[d,j\])-(m\[i+1,d\]+m\[d,j\]+m\[i,k\]+m\[k,j\])

=(m\[i+1,k\]+m\[i,d\])-(m\[i+1,d\]+m\[i,k\])

∵m满足四边形不等式，∴对于i<i+1≤k<d有m\[i+1,k\]+m\[i,d\]≥m\[i+1,d\]+m\[i,k\]

∴(mk\[i+1,j\]-md\[i+1,j\])≥(mk\[i,j\]-md\[i,j\])≥0

∴s\[i,j\]≤s\[i+1,j\]，同理可证s\[i,j-1\]≤s\[i,j\]

证毕

## 2扩展 ##

[编辑][Link 5]

以上所给出的状态转移方程只是一种比较一般的，其实，很多状态转移方程都满足四边形不等式优化的条件。

解决这类问题的大概步骤是：

0.证明w满足四边形不等式，这里w是m的附属量，形如m\[i,j\]=opt\{m\[i,k\]+m\[k,j\]+w\[i,j\]\}，此时大多要先证明w满足条件才能进一步证明m满足条件

1.证明m满足四边形不等式

2.证明s\[i,j-1\]≤s\[i,j\]≤s\[i+1,j\]

参考题解：[https://www.luogu.org/blog/Hurricane-zjz/solution-p1880][https_www.luogu.org_blog_Hurricane-zjz_solution-p1880]

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define Maxn 210
    #define INF 0x7fffffff
    int sum[Maxn];
    int Fmin[Maxn][Maxn];
    int Fmax[Maxn][Maxn];
    int s[Maxn][Maxn];
    int n;
    
    int main()
    {
    	//freopen("1.txt","r",stdin);
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    	{
    		cin >> sum[i];
    		sum[i + n] = sum[i];
    	}
    	for (int i = 1; i <= 2 * n; i++)
    		sum[i] += sum[i - 1],s[i][i] = i;;
    	//for (int i =1; i<=2*n-1; i++)
    	for (int i=2*n-1;i; i--)//不太明白为什么从2*n-1~1
    	{
    		for (int j = i+1; j <= 2 * n; j++)
    		{
    			Fmax[i][j] = max(Fmax[i][j - 1], Fmax[i + 1][j]) + sum[j] - sum[i - 1];
    			int tmp = INF;
    			//int k;
    			int index=0;
    			for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++)
    			{
    				int tt = Fmin[i][k] + Fmin[k + 1][j] + sum[j] - sum[i - 1];
    				if (tmp > tt)
    				{
    					tmp = tt;
    					index = k;
    				}
    			}
    			Fmin[i][j] = tmp;
    			//cout << Fmin[i][j] << ' ';
    			s[i][j] = index;
    		}
    		//cout << '\n';
    	}
    	int ans_max = 0;
    	int ans_min = INF;
    	for (int i = 1; i <= n; i++)
    	{
    		ans_max = max(ans_max, Fmax[i][n + i - 1]);
    		ans_min = min(ans_min, Fmin[i][n + i - 1]);
    	}
    	cout << ans_min << '\n' << ans_max;
    	return 0;
    }

[70]: /images/20220527/a20b0fabcb7d4db39e468fd697c5d7f9.png
[Link 1]: https://baike.sogou.com/Create.e?sp=2&sp=l57409469&sp=1
[Link 2]: https://baike.sogou.com/v57921445.htm
[Link 3]: https://baike.sogou.com/v37255466.htm
[Link 4]: https://baike.sogou.com/v179978.htm
[Link 5]: https://baike.sogou.com/Create.e?sp=2&sp=l57409469&sp=2
[https_www.luogu.org_blog_Hurricane-zjz_solution-p1880]: https://www.luogu.org/blog/Hurricane-zjz/solution-p1880