首页 > 其他分享 >由POJ1821得出的一些dp优化技巧

由POJ1821得出的一些dp优化技巧

时间:2024-02-29 10:26:49浏览次数:25  
标签:这个 技巧 int POJ1821 循环 优化 dp

比如

  for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=dp[i-1][j];
		}
		for(int l=max(1,s[i]-l[i]+1);l<=s[i];l++){
            for(int r=s[i];r<=min(n,l+l[i]-1);r++){
                dp[i][r]=max(dp[i][r],dp[i-1][l-1]+p[i]*(r-l+1));
            }
		}
	}

这个dp显然可以优化,但是这个不好优化,因为我的方程是dp[i][r]=......,然而i在第一层循环,而r在第三层循环,中间加了一个l。但是我们只要将二三两层循环调换位置就可以了。
又比如

for(int i=1;i<=m;i++){
		for(int j=0;j<=n;j++){
			dp[i][j]=dp[i-1][j];
		}
		for(int len=1;len<=l[i];len++){
			for(int l=max(1,s[i]-len+1);(l<=s[i])&&(l+len-1<=n);l++){
				int r=l+len-1;
				dp[i][r]=max(dp[i][r],dp[i-1][l-1])+p[i]*len;
			}
		}
	}

这个和上面一样,但是这个也不好优化,虽然也有上面的问题,但是这个还有一个问题。可以看到这里的r是通过len和l间接求出来的,这样显然是不好的,所以dp里面的东西一定要在循环上枚举。

标签:这个,技巧,int,POJ1821,循环,优化,dp
From: https://www.cnblogs.com/wuhupai/p/18042787

相关文章

  • 14 CodeTON Round 5 (Div. 1 + Div. 2, Rated, Prizes!)C. Tenzing and Balls(dp+前缀
    思路:dp还是挺明显的,思路可以参考最长上升子序列有点dp的感觉\(f[i]\)表示考虑前\(i\)个数,的最大值当前数有两种删或不删不删:\(f[i]=f[i-1]\);删:\(f[i]=max{f[j-1]+i-j+1}\)这个转移是\(O(n^2)\)的显然时间上来不及考虑优化,第一层循环一定是省不了的考虑优化掉第二层循环......
  • 花神的数论题(数位dp)
    花神的数论题题目描述设\(\text{sum}(i)\)表示\(i\)的二进制表示中\(1\)的个数。给出一个正整数\(N\),花神要问你\(\prod_{i=1}^{N}\text{sum}(i)\),也就是\(\text{sum}(1)\sim\text{sum}(N)\)的乘积。数据范围\(1\leN\le10^{15}\)。解法首先我们要......
  • 人工智能水印技术入门:工具与技巧
    近几个月来,我们看到了多起关于“深度伪造(deepfakes)”或人工智能生成内容的新闻报道:从泰勒·斯威夫特的图片、汤姆·汉克斯的视频到美国总统乔·拜登的录音。这些深度伪造内容被用于各种目的,如销售产品、未经授权操纵人物形象、钓鱼获取私人信息,甚至制作误导选民的虚假资料,它......
  • 旅游景点 Tourist Attractions (壮压 DP)题解
    简化题意题目链接——不卡内存班题目链接——卡内存版给定\(n\)个点和\(m\)条边组成的无向图,按照一定限制要求停留\(2\simk+1\)共\(k\)个点(可以经过但不停留),求最短的从\(1\)出发到\(n\)的路径长。限制情况如下:共有\(q\)个限制,接下来\(q\)行,每行两个数\(x......
  • 状压dp
    0.位运算1.概述用01数字标志状态2.要求对象状态只能有两种,例如放/不放,正/反等等某一项指标的范围很小3.实际运用后续\(S_i\)一般表示状态(除特殊说明)特殊方格棋盘click组合:我会!\(n!\)先考虑所有格子都能放\(n\leqslant20\),可以状压\(0\)表示没放,\(1\)表示放......
  • vim括号匹配等跳转技巧
    %跳转到相配对的括号gD跳转到局部变量的定义处''跳转到光标上次停靠的地方,是两个',而不是一个"mx设置书签,x只能是a-z的26个字母,"`x"跳转到书签处>增加缩进,"x>"表示增加以下x行的缩进<减少缩进,"x<"表示减少以下x行的缩进{跳到上一段的开头}跳到下一段的的......
  • Windows如何检测UDP端口的连通性
    在Windows平台上如何检测UDP端口的连通性呢?其实,平时我们遇到检测TCP端口的连通性的情况比较多,遇到检测UDP端口连通性的情况较少。而且检测UDP端口的连通性比较复杂一点。像检测TCP端口是否连通(放开),Windows平台,一般常用的工具有telnet、psping等工具,而检测UDP端口的工具,在Linux平台......
  • SpringBoot 2x 系列之(五)开发技巧
    开发技巧1.Lombok1.应用场景简化JavaBean的开发帮我们在编译时生成get、set、toString方法2.安装及使用引入依赖【SpringBoot已经做了版本仲裁】<dependency><groupId>org.projectlombok</groupId><artifactId>lombok</artifactId></depende......
  • dp练习
    合并类len=2,[k]消消乐类,len=3,[i+1][j-1]else[k]Bracketshttps://vjudge.net/problem/POJ-2955#include<iostream>#include<cstring>usingnamespacestd;intdp[101][101];boolflag=1;boolpei(inti,intj,chara[]){if(a[i]=='('&&......
  • 基于STM32F407MAC与DP83848实现以太网通讯四(STM32F407MAC数据收发与DMA描述符)
    上一章实现的MAC数据包的基础收发功能,但是只是简单的操作了ETH外设的收发包函数并没有深入了解其中的原理逻辑,本章结合STM32F40x文档与STM32F4x7_ETH_Driver驱动库了解MAC的收发包流程。一、描述符列表 在创建描述符列表之前先了解描述符列表的定义,描述符就软件来说就是一个结......