信息学奥赛一本通 1923：【03NOIP普及组】数字游戏

2024-07-11 22:28| 来源: 网络整理| 查看: 265

【题目链接】

ybt 1923：【03NOIP普及组】数字游戏洛谷 P1043 [NOIP2003 普及组] 数字游戏

【题目考点】 1. 区间动规【解题思路】

首先做“破环为链”，将有n个元素的环形序列变为有2n-1个元素的线性序列。记第i个元素值为a[i]。求出前缀和数组s，然后求出v数组，v[i][j]表示第i到第j元素加和后对10取模的值。以下给出求最大乘积的方法，求最小乘积与该方法类似。

1. 状态定义集合：将n个数分成m个部分的方案限制：将第i到第j个数分成k部分属性：每个部分对10取模后的乘积条件：最大统计量：乘积

状态定义：dp[i][j][k]：将第i到第j个数分成k部分的所有方案中，每个部分对10取模后的乘积值最大的那个方案的乘积的值。初始状态：如果k为1，那么将第i到第j个数分成1部分，乘积值为v[i][j]，即dp[i][j][1] = v[i][j]

2. 状态转移方程

集合：将第i到第j个数分成k部分的方案分割集合：第k部分左端点为分割点，枚举分割点

如果第k部分左端点为j，那么第k部分为a[j]，k个部分乘积的最大值，为将i~j-1分为k-1个部分乘积的最大值dp[i][j-1][k-1]乘以第k部分的值v[j][j]，即dp[i][j][k] = dp[i][j-1][k-1]*v[j][j]如果第k部分左端点为j-1，那么第k部分为a[j-1]~a[j]，k个部分乘积的最大值，为将i~j-2分为k-1个部分乘积的最大值dp[i][j-2][k-1]乘以第k部分的值v[j-1][j]，即dp[i][j][k] = dp[i][j-2][k-1]*v[j-1][j] …如果第k部分左端点为i+k-1，那么第k部分为a[i+k-1]~a[j]，k个部分乘积的最大值，为将i~i+k-2分为k-1个部分(每个部分有1个数字）乘积的最大值dp[i][i+k-2][k-1]乘以第k部分的值v[i+k-1][j]，即dp[i][j][k] = dp[i][i+k-2][k-1]*v[i+k-1][j]综上，设第k部分的左端点为h，h从i+k-1循环到j，每次取到的第i到第j数字分为k个部分乘积的最大值为dp[i][j][k] = dp[i][h-1][k-1]*v[h][j]，以上各种情况取最大值。如要求最小乘积，则在以上各情况中取最小值。 3. 具体实现

为最大值与最小值分别设一个状态数组。注意求v[i][j]时，左端i可以超过n的，要判断右端j小于2n。求dp数组时，左端i最多就是n，i大于n的情况无意义。该题要使用区间动规的写法，先枚举区间长度从1到n，然后确定左端点i，再确定右端点j。在递推求出状态后，需要遍历长为n的所有区间，比较将长为n的区间分为m部分的乘积，求出两状态数组中的最大值和最小值。

【题解代码】解法1：区间动规 #include using namespace std; #define N 105 #define INF 0x3f3f3f3f int m, n, a[N], s[N], v[N][N];//a[i]:第i元素 s:前缀和 v[i][j]:a[i]~a[j]加和对10取模的值 int dpx[N][N][10], dpn[N][N][10];//dpx[i][j][k]:将第i到第j个数分成k部分的所有方案中，每个部分对10取模后的乘积值最大的那个方案的乘积的值。 dpn:乘积最小值 int Mod10(int a)//正数或负数a模10得到非负数 { if(a >= 0) return a % 10; else return a % 10 + 10; } int main() { cin >> n >> m; for(int i = 1; i int j = i+l-1; v[i][j] = Mod10(s[j]-s[i-1]); } memset(dpn, 0x3f, sizeof(dpn));//求最小值的数组初值设为无穷大 for(int l = 1; l dpx[i][j][k] = max(dpx[i][j][k], dpx[i][h-1][k-1]*v[h][j]); dpn[i][j][k] = min(dpn[i][j][k], dpn[i][h-1][k-1]*v[h][j]); } } int mx = 0, mn = INF; for(int i = 1; i

【本文地址】

公司简介

联系我们