普及模考T3题解

经验分享区
1

这道题目看似是博弈，但是其实是区间 dp！

首先区间 dp 的板子大家一定要记住：

for(int len=2;len<=n;len++) {//先枚举区间长度
	for(int i=1;i+len-1<=n;i++) {//再枚举区间左端点，左端点加区间长度为右端点，不能大于n
		int j=i+len-1;	//区间右端点
		for(int k=i;k<j;k++) {	//枚举区间分割点
			dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+/*合并区间的消耗*/);
		}
	}
}

简单认识模板以后我们就可以来求此题了，放上 dp 的要素：

  1. 定义： dp[i][j] 表示在区间 i 到 j 中 dogwang 的最大的得分的最小值。
  2. 初始化：因为我们要求最小值所以将 dp 数组初始化为无穷大，并且对于 dp[i][i] 的类型初始化为 0 因为 dogeya 将这唯一一个元素取走后，答案只能为 0 并且为了防止以后在状态转移的时候出现左端点大于右端点的情况，我们将 dp[i+1][i] 也初始化为 0 。
  3. 状态转移：我们枚举区间中的一个下标 k 设 dogeya 取走了这个下标的元素，那么整个区间被我们分成了 2 段，第一段是 [l,k-1] 第二段是 [k+1,r] 我们分别求出这两种情况的最大值，最后再与 dp[l][r] 取最小值即可。
  4. 答案：游戏在 [1,n] 中进行，所以答案为 dp[1][n] 。

接下来通过要素来写代码：

    /*初始化*/
    for(int len=2;len<=n;len++){//枚举区间长度
        for(int l=1;l+len-1<=n;l++){//枚举左端点
            int r=l+len-1;//右端点
            for(int k=l;k<=r;k++)dp[l][r]=min(dp[l][r],max(sum[k-1]-sum[l-1]+dp[k+1][r],sum[r]-sum[k]+dp[l][k-1]));//状态转移
        }
    }
    /*输出*/
1 个赞