说明讲稿某题解.pptx

  1. 1、本文档共26页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多

某题解

先最简单的吧T1

先最简单的吧T1略去读题题目要求就是N*M矩阵中横或竖切K刀,使得所有块的和组成的数列方差最小

先最简单的吧T1略去读题题目要求就是N*M矩阵中横或竖切K刀,使得所有块的和组成的数列方差最小注意到某差公式 实际上可以化简

先最简单的吧T1不难发现后面的是常数题目就简化成了分成K块使得K块和的平方和最小

先最简单的吧到此有一点DP的味道了方便讲起见我们简化一下题目一个长为N的数列分M段使得每段数值的和的平方和最小N=100

先最简单的吧到此有一点DP的味道了方便讲起见我们简化一下题目一个长为N的数列分M段使得每段数值的和的平方和最小N=100100的话N^2M稳稳的DPM[i][j]=min{DPM[k][j-1]+(Sum[i]-Sum[k])^2}

先最简单的吧DPM[i][j]=min{DPM[k][j-1]+(Sum[i]-Sum[k])^2}DPM[i][j]表示前i个数划分成j段的最优答案DP的思想貌似和分冶有点相似是把一个区间的最优解分冶成几个小区间的最优解然后转移,最后得到全局最优解的通过这个思想我们可以得出这道题的DP方程DP[ix][iy][jx][jy][k]表示以(ix,iy)为左上角以(jx,jy)为右下角的矩形,切k块的最优解

那么对于横着切DPM[ix][iy][jx][jy][k]= min{DPM[ix][iy][mid][jy][ak]+DPM[mid+1][iy][jx][jy][k-ak-1]}以及竖着切DPM[ix][iy][jx][jy][k]= min{DPM[ix][iy][jx][mid][ak]+DPM[ix][mid+1][jx][jy][k-ak-1]}这样就可以转移了边界条件DPM[ix][iy][jx][jy][0]=(sumfrom(ix,iy)to(jx,jy))^2先最简单的吧

先最简单的吧至此T1讲完了5维DP,复杂度O(A^3B^2K^2+A^2B^3K^2)差不多就是O(N^7)2E8的复杂度有点不稳因为可以二重三角优化,其实还是随便跑的原题P2217[HAOI2007]分割矩阵个人觉得难度提高-

接下来不是T2T3可以想象是N天每天先得到一些钱,在判断是否购买这一点的商品要求最后买的商品最多且任何时刻不能欠债

接下来不是T2T3可以想象是N天每天先得到一些钱,在判断是否购买这一点的商品要求最后买的商品最多且任何时刻不能欠债你们都是dalao了啊,没有纯粹暴力分40%的数据N,M=100

接下来不是T2T340%的数据N,M=100可以写出DP方程DP[N][M]表示第N天后手里有M钱,能买到的最多个数那么可以写出程序DP[0][0]=0ForIfrom1ton forjfrom0ton*n DP[i][j]=max(DP[i-1][j-Get[i]], DP[i-1][j-Get[i]+Cost[i]]+1)

接下来不是T2T340%的数据本质和背包差不多复杂度O(N∑M)就是O(N^3)然后是70%的数据N,M=10000很明显O(N^3)的话wys也救不了你这时候可以DP换状态来枚举

接下来不是T2T340%的数据本质和背包差不多复杂度O(N∑M)就是O(N^3)然后是70%的数据N,M=10000很明显O(N^3)的话wys也救不了你这时候可以DP换状态来枚举 DP[i][j]表示第i个物品后买了j个物品时手中能有的最大钱数DP[i][j]合法当且仅当DP[i][j]=0

接下来不是T2T3然后是70%的数据N,M=10000可以写出DP来DP[0][0]=0ForIfrom0ton-1 forjfrom0toI if(DP[i][j]=0) DP[i+1][j]min=DP[i][j]+Get[i] DP[i+1][j]min=DP[i][j]+Get[i]- Pay[j]答案是最大的j且DP[N][j]=0

接下来不是T2T3100%的数据N=100000M=1E9很明显发现无论如何状态存不下一维也保存不了状态然后就可以放弃想DP了正解是贪心贪心策略1:能买就买,不买白不买贪心策略2:如果今天买不了,但是可以再省钱,如果以前某一天买的比今天这个贵, 那可以直接退货换成这个补差价,尽量优化钱数

接下来不是T2T3贪心策略1没什么好说的贪心策略2如果满足自然要找以前买过最贵的来换不太清楚什么算是严谨的证明..假设第K天的状态是最优的就是最多能买一定土地且手上剩余钱数也是最优的那么K+1天能买就买一定对K+1天是最优的如果买不了的话肯定做不到买更多土地所以只能从手上剩余钱数下手了,尝试把今天的一中家属院与以前买的北京二环

文档评论(0)

159****9610 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:6044052142000020

1亿VIP精品文档

相关文档