首页 > 其他分享 >挑程:矩阵乘积链(区间dp)

挑程:矩阵乘积链(区间dp)

时间:2023-09-01 12:15:29浏览次数:41  
标签:乘积 int solve 区间 挑程 dp

传送

区间dp

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int p[N],dp[N][N];
void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    cin>>p[i-1]>>p[i];
    memset(dp,0x3f,sizeof dp);
    for(int i=1;i<=n;++i) dp[i][i]=0;
    for(int l=2;l<=n;++l)
     for(int i=1;i<=n;++i)
     {
     	int j=i+l-1;
     	if(j>n) break;
     	for(int k=i;k<j;++k)
     	{
     		dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]);
     	}
     }
    cout<<dp[1][n]<<'\n'; 
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}

标签:乘积,int,solve,区间,挑程,dp
From: https://www.cnblogs.com/ruoye123456/p/17671502.html

相关文章

  • 2023下半年武汉/成都/深圳NPDP产品经理国际认证开班啦
    产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。  【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是全球范围内产品开发与管理专业人士最杰出的倡导者,协助个人、企业......
  • 用SharedPreferences写的存储工具类
    读写更方便publicclassPersistenceUtil{ privateContextcontext; publicContextgetContext(){ returncontext; } publicvoidsetContext(Contextcontext){ this.context=context; } publicPersistenceUtil(Contextcontext){ this.context=contex......
  • 动态规划-区间DP
    动态规划-区间DP1.区间DP的概念区间DP,顾名思义就是在一个个的区间上进行DP。2.区间DP问题-石子合并https://www.acwing.com/problem/content/284/我们还是从动态规划的两个角度来阐述该问题。1.状态表示本问题,我们可以用二维状......
  • Java - ThreadPoolExecutor线程池分析
    Java- ThreadPoolExecutor源码分析 1.为什么要自定义线程池首先ThreadPoolExecutor中,一共提供了7个参数,每个参数都是非常核心的属性,在线程池去执行任务时,每个参数都有决定性的作用。但是如果直接采用JDK提供的方式去构建,可见设置的核心参数最多就两个,这样就会导致对线程池......
  • 状压DP总结
    动态规划-状压类-总结状压类的题,一般都需要用到二进制的性质。(用到组合数概率也不小)母题2:考虑用二进制表示摆放方式,然后使用位运算判断攻击。变式有一位很小,状压,状态类似于母题。变式2有交换操作,所以与逆序对相关,然后数学讨论一下,再状压。变式3考虑用集合、余数表示,注意......
  • PyTorch多卡分布式训练DDP单机多卡
    前言因为课题组发的卡还没有下来,先向导师问了实验室的两张卡借用。之前都是单卡训练模型,正好在这个机会实践以下单机多卡训练模型的方法。关于DDP网上有很多资料,但都比较零碎(有些博客的代码甚至没办法run),Pytorch给出的官方文档看起来也比较吃力。因此这篇文章的主要目的是......
  • 使Windows11支持同时多个用户远程桌面连接(RDP)
    参考:https://www.wyr.me/post/701一、配置远程桌面服务更改限制连接的数量将用户限制到单独的远程桌面服务会话(可选)二、为termsrv.dll增加修改权限C:\Windows\System32\termsrv.dll详情请参考:https://www.wyr.me/post/701三、停止RemoteDesktopServices服务打开......
  • 使用第三方RDP(远程桌面)客户端远程连接Windows10/11
    一、打开「编辑组策略」并定位  二、指定RDP为安全层三、禁用「要求使用网络级别的身份验证……」......
  • 服务器Nginx环境如何配置WordPress伪静态规则
    WordPress伪静态是指将动态生成的WordPress网站页面的URL转换为静态的URL,以便于搜索引擎优化和提高用户访问体验。与动态URL相比,静态URL更容易被搜索引擎索引,因为它们更具可读性和可理解性,同时也更容易被用户记住和分享。最近看到有粉丝在问服务器Nginx环境下如何配置......
  • AcWing - 闫氏DP分析法
    核心思想:从集合角度来分析DP问题在我们遇到的DP问题中,一般都是求在一个有限集内的最值,但是这些方案数量一般都是指数级别的,想要一个一个查找出来不太可能。所以DP方法是用来优化这种寻找最优方案的过程的。DP问题一般来说分析时都要经过两个阶段:状态表示(化零为整):指把一些具有......