首页 > 其他分享 >[动态规划] 区间 dp

[动态规划] 区间 dp

时间:2024-05-18 09:07:49浏览次数:26  
标签:得分 子树 min int max 区间 动态 dp

区间 dp

石子合并

将区间长度 \(len\) 作为 \(dp\) 的阶段

设 \(f[l][r]\) 表示把最初的第 \(l\) 堆到第 \(r\) 堆石子合并成一堆,需要消耗的最少体力。

合并代价就是这两堆石子的质量和,这里可以用前缀和直接计算,设 \(s[i]\) 表示前 \(i\) 堆石子的质量和。

状态转移方程:

\[f[l][r] = \min_{l≤k<r}^{}\{f[l][k]+f[k+1][r]+(s[r]-s[l-1])\} \]

计算 max 同理

注意,由于需要破环为链,不能直接将答案返回 \(f[1][n]\) ,要在计算过程中更新答案。

int f[N][N];
int n;
int a[N], s[N];

int cost(int l, int r){return s[r] - s[l - 1];}

int dp_min()
{
    int minn = inf;
    for (rint len = 1; len < n; len++)
    {
    	for (rint l = 1; l <= 2 * n - len; l++)
    	{
    		int r = l + len;
    		f[l][r] = inf;
    		for (rint k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + cost(l, r));
			if (len + 1 == n) minn = min(minn, f[l][r]);
		}
	}
	return minn;
}

int dp_max()
{
	int maxx = 0;
	for (rint len = 1; len < n; len++)
	{
		for (rint l = 1; l <= 2 * n - len; l++)
		{
			int r = l + len;
			f[l][r] = 0;
			for (rint k = l; k < r; k++) f[l][r] = max(f[l][r], f[l][k] + f[k + 1][r] + cost(l, r));
			if (len + 1 == n) maxx = max(maxx, f[l][r]);
		}
	}
	return maxx;
}

signed main()
{
    cin >> n;
    for (rint i = 1; i <= n * 2; i++)
    {
    	if (i <= n)
		{
			cin >> a[i];
			a[i + n] = a[i];
		}
    	s[i] = s[i - 1] + a[i];
	}
	cout << dp_min() << endl << dp_max() << endl;
	return 0;
}

P4342 [IOI1998] Polygon

本题要求的是区间合并的最大得分,很明显是区间 \(dp\) 问题。

把被删除的边逆时针方向的顶点称为 "第 \(1\) 个顶点",依此类推。然后用区间 \(dp\) 常见的状态表示。

设 \(f[l][r]\) 表示把第 \(l\) 到 \(r\) 个顶点合成的最大得分。

状态表示没有什么问题,但是状态转移出现了问题,我们并不能通过 \(f[l][k]\) 和 \(f[k + 1][r]\) 来得到 \(f[l][r]\)

有可能 \(l\) ~ \(k\) 的某种得分是负数 \(a\),\(k + 1\) ~ \(r\) 的某种得分也是负数 \(b\),但是 \(a * b\) 可能比 \(f[l][k] * f[k + 1][r]\) 更大。

由此得出状态转移的错误性,那么我们应该如何得出 \(f[l][r]\) 呢,首先分析 \(l ~ r\) 的最大得分有几种可能得到:

  1. max(l ~ k) + max(k + 1 ~ r)
  2. max(l ~ k) * max(k + 1 ~ r)
  3. min(l ~ k) * min(k + 1 ~ r) (负负得正)

通过分析可以发现,要想得出 \(f[l][r]\) 需要知道子状态的最大值和最小值。

设 \(f[l][r][0]\) 表示把第 \(l\) 到 \(r\) 个顶点合成的最大得分,\(f[l][r][1]\) 表示把第 \(l\) 到 \(r\) 个顶点合成的最小得分

那么我们每次转移都需要转移最大值和最小值,上面已经分析最大值的转移,再分析一下最小值的转移:

  1. min(l ~ k) + min(k + 1 ~ r)
  2. min(l ~ k) * min(k + 1 ~ r)
  3. max(l ~ k) * max(k + 1 ~ r)
  4. max(l ~ k) * min(k + 1 ~ r)
  5. min(l ~ k) * max(k + 1 ~ r)

起始状态为 \(f[i][i][0] = f[i][i][1] = a[i]\),结束状态为 \(f[1][n][0]\)

以上就是全部的状态转移,另外还需要考虑第一步要删除哪条边。这里采用拆环成链的技巧,例如,将 - a - b - c - d - 拆成 a - b - c - d - a - b - c - d 这时枚举所有以前一半为端点的链,就能找出所有的情况。

a - b - c - dd - a

b - c - d - aa - b

c - d - a - bb - c

d - a - b - cc - d

最终枚举所有的链从中取最大值即可。

int n;
int a[N]; 
//原序列
char op[N]; 
//操作序列
//f[l][r][0] 表示把第 l 到 r 个顶点合成的最大得分
//f[l][r][1] 表示把第 l 到 r 个顶点合成的最小得分
int f[N][N][2];

signed main()
{
    cin >> n;

    //接收原序列、操作序列
    for (rint i = 1; i <= 2 * n; i++)
        if (!(i % 2)) cin >> a[i / 2];
        else scanf("%s", &op[(i + 1) / 2]);

    //初始化
    for (rint l = 1; l <= 2 * n; l++)
        for (rint r = 1; r <= 2 * n; r++)
            f[l][r][0] = -inf, f[l][r][1] = inf;

    //拆环成链
    for (rint i = 1; i <= n; i++)
    {
        a[i + n] = a[i];
        op[i + n] = op[i];
        f[i][i][0] = f[i + n][i + n][0] = f[i][i][1] = f[i + n][i + n][1] = a[i]; 
    }

    for (rint len = 1; len < n; len++) 
    {
        for (rint l = 1; l + len <= 2 * n; l++)
        {
            int r = l + len; 
            for (rint k = l; k < r; k++) 
                if (op[k + 1] == 't') //加法
                {
                    f[l][r][0] = max(f[l][r][0], f[l][k][0] + f[k + 1][r][0]);
                    f[l][r][1] = min(f[l][r][1], f[l][k][1] + f[k + 1][r][1]);
                }
                else //乘法
                {
                    f[l][r][0] = max(f[l][r][0], f[l][k][0] * f[k + 1][r][0]);
                    f[l][r][0] = max(f[l][r][0], f[l][k][1] * f[k + 1][r][1]);
                    f[l][r][1] = min(f[l][r][1], f[l][k][1] * f[k + 1][r][1]);
                    f[l][r][1] = min(f[l][r][1], f[l][k][1] * f[k + 1][r][0]);
                    f[l][r][1] = min(f[l][r][1], f[l][k][0] * f[k + 1][r][1]);
                    f[l][r][1] = min(f[l][r][1], f[l][k][0] * f[k + 1][r][0]);
                }
        }		
	}

    //枚举所有链取最大值
    int res = -inf;
    for (rint i = 1; i <= n; i++) res = max(res, f[i][i + n - 1][0]);
    cout << res << endl;

    //找出所有能取到最大值的顶点
    for (rint i = 1; i <= n; i++)
        if (res == f[i][i + n - 1][0])
            cout << i << " ";

    return 0;
}

AcWing 284. 金字塔

设 \(f[l][r]\) 表示子串 \(s[l\) ~ \(r]\) 对应多少种可能的树形结构。

然后考虑对区间的划分,根据区间的划分不同,也可能得出不同的树形结构。

若 \(s[l\) ~ \(r]\) 对应一棵子树,那么 \(s[l]\) 和 \(s[r]\) 就应该是树根,\(s[l + 1]\) 和 \(s[r - 1]\) 就是进入和离开子树时的节点。
除此之外,\([l, r]\) 包含的每棵更深的子树都对应一个子问题,会产生 \([l, r]\) 中的一段,相邻两段之间还有途经树根产生
的一个字符。由于 \([l, r]\) 包含的子树个数可能不止两个,如果我们朴素的枚举划分点的数量和所有划分点的位置,那么
时间复杂度会高得离谱。

因此我们可以换种思路,尝试把 $s[l $ ~ $ r]$ 分成两部分,每部分可由若干棵子树组成,不过这样可能会产生重复计数。

如果每段都可以由多棵子树构成,如 "ABABABA",划分成 "A|BAB|A|B|A" 和 "A|B|A|BAB|A",其中 "BAB" 都能产生 "B|A|B"
两棵子树,那么这两种划分方式最终就会变成同一种结果。

为了解决不重不漏,我们可以只考虑子串 \([l\) ~ \(r]\) 的第一棵子树时由哪一段构成的,枚举划分点$ k$,令子串 \(s[l + 1\) ~ \(k - 1]\)
构成 \([l, r]\) 的第一棵子树,\(s[k\) ~ \(r]\) 构成 \([l, r]\) 的剩余部分(其他子树)。

如果 \(k\) 不相同,那么子串 \(s[l + 1\) ~ \(k - 1]\) 代表的子树的大小也不相同,就不可能产生重复计算的结构。

由此得出状态转移方程,当 \(s[l]≠s[r]\)

\[f[l][r]=0 \]

当 \(s[l]=s[r]\)

\[f[l][r]=f[l+1][r-1]+\sum_{l+2≤k≤r-2,s[l]=s[k]}{f[l+1][k-1]*f[k][r]} \]

起始状态为 \(f[i][i] = 1\),目标状态为 \(f[1][n]\)

char str[N];
int f[N][N]; 
//表示子串 s[l ~ r] 对应多少种可能的树形结构

int dfs(int l, int r)
{
    if (l > r) return 0; //不合法的状态方案数为 0
    if (l == r) return 1; //一个节点无法划分,方案数为 1
    if (f[l][r] != -1) return f[l][r]; //如果当前区间已经计算过,直接返回结果
    if (str[l] != str[r]) return 0; //不是一棵完整的子树,方案数为 0
    //到这说明当前区间没计算过
    f[l][r] = 0; //最开始方案数为 0
    for (rint k = l + 2; k <= r; k++) //枚举划分点
        f[l][r] = (f[l][r] + dfs(l + 1, k - 1) * dfs(k, r)) % mod; //累加方案数
    return f[l][r]; //将 [l ~ r] 的方案数往回传
}

signed main()
{
    scanf("%s", str + 1);
    memset(f, -1, sizeof f); //记忆化搜索初始化,没有计算过的状态默认为 -1
    cout << dfs(1, strlen(str + 1)) << endl; //递归计算整个区间
    return 0;
}

标签:得分,子树,min,int,max,区间,动态,dp
From: https://www.cnblogs.com/spaceswalker/p/18199018

相关文章

  • WordPress古腾堡编辑器和经典编辑器详细对比,哪个好用?
    WordPress古腾堡编辑器(GutenbergEditor)是WordPress5.0版本引入的默认编辑器,取代了之前的经典编辑器。古腾堡编辑器的设计理念是基于“块”(blocks),让用户能够更直观、灵活地编辑内容。WordPress经典编辑器是WordPress5.0版本之前的默认编辑器,它采用传统的单个文本框界面,用户可以......
  • C122 李超树合并+DP CF932F Escape Through Leaf
    视频链接:C122李超树合并+DPCF932FEscapeThroughLeaf_哔哩哔哩_bilibili   C65【模板】线段树合并P4556[Vani有约会]雨天的尾巴-董晓-博客园(cnblogs.com)CF932FEscapeThroughLeaf#include<iostream>#include<cstring>#include<algorithm>using......
  • vue3+vite,写动态路由时候遇到的坑
    import导入一直报错,看了网上说import不行要写成 require之类的,都试了个遍,结果还是不行。一个很容易犯的错误:理所当然的以为alias是可以使用的。事实上写全相对路径就可以了!!! letr=awaitapis['common/getRouteList']()constlist=r.map((t)=>({id:t.id,pid......
  • 动态排序
    usingDynamicSort;usingMicrosoft.EntityFrameworkCore;List<StudnetEntity>studentList=newList<StudnetEntity>(){newStudnetEntity(){Name="Chen",Age=28},newStudnetEntity(){Name="Wang",Age=29}};......
  • 关于IDEA使用xml实现动态sql的问题
     如上图,我在mapper层编写了一个list方法用于实现动态sql。1.导入使用xml文件的mybatis依赖。 2.配置文件的修改.properties .yml mybatis.mapper-locations=classpath:mapper/*.xml:这个配置项指定了MyBatis映射器XML文件的位置。值classpath:mapper/*.xml......
  • macOS开发,如何设置动态桌面壁纸(动态壁纸酷)
    1.首先要先建立一个全屏的窗口1//获取窗口控制器2NSStoryboard*storyboard=[NSStoryboardstoryboardWithName:@"Main"bundle:[NSBundlemainBundle]];3WallpaperWindowController*wwc=[storyboardinstantiateControllerWithIdentifier:@"AboutWindowController......
  • 线头 DP 问题
    引入对于一种需要通过相邻两项来维护的一些DP问题,通常的DP会无法转移。这时便要使用线头DP。这种DP又名连续段DP,其关键在于维护已近满足条件的不同连续段的贡献总和。线头DP本质上只是一种转移状态,这种状态能与排列成双射的同时,还能只考虑两端的性质来使状态便于记录......
  • 实战项目-基于K8s平台进行wordpress建站
    (240516更新)基本信息系统:Debian12.05k8s版本:1.30环境:虚拟机序号IP地址域名主机名1192.168.100.12k8s-master.$yourname.comk8s-master2192.168.100.15k8s-node1.yourname.comk8s-node13192.168.100.16k8s-node2.yourname.comk8s-node24192.168......
  • 国产linux系统(银河麒麟,统信uos)使用 PageOffice 国产版在线动态填充 word 文件
    PageOffice国产版:支持信创系统,支持银河麒麟V10和统信UOS,支持X86(intel、兆芯、海光等)、ARM(飞腾、鲲鹏、麒麟等)芯片架构。在实际的Word文档开发中,经常需要自动填充数据到Word模板中,以生成动态的Word文档。例如,我们可以根据数据库表中已保存的个人信息,设计好一个简历模板docx文件,......
  • 动态规划
    ABC207EModi显然有\(n^3\)的dp。设\(f_{i,j}\)表示前\(i\)个数里划分\(j\)段(\(i\)为第\(j\)段结尾)的方案数,\(s_i=\sum_{i=1}^ia_i\),则有:\[f_{i,1}=1,f_{i,j}=\sum_{k=1}^{i-1}[s_i-s_k\equiv0\pmodj]f_{k,j-1}\]考虑进一步优化。我们发现上式可以化为:\[f_{......