首页 > 其他分享 >线性dp

线性dp

时间:2023-11-20 19:01:06浏览次数:28  
标签:const int namespace 1e9 线性 dp

1.数字三角形。acwing 898.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int N = 520,INF = 1e9;
 5 int n;
 6 int a[N][N]; //表示每一个点
 7 int f[N][N]; //表示状态
 8 
 9 int main()
10 {
11     cin >> n;
12     for (int i = 1; i <= n; i ++ )
13        for (int j = 1; j <= i; j ++ )
14            cin >> a[i][j];
15     
16     for (int i = 0; i <= n; i ++ )
17        for (int j = 0; j <= i + 1; j ++ ) //每行多初始化一个,表示三角形最右边的右上角表示负无穷
18           f[i][j] = -INF; //避免处理边界情况,先将状态初始化为负无穷
19     
20     f[1][1] = a[1][1];
21     
22     for (int i = 2; i <= n; i ++ )
23        for (int j = 1; j <= i; j ++ )
24        f[i][j] = max(f[i - 1][j - 1] + a[i][j],f[i - 1][j] + a[i][j]);
25     
26     int res = -INF;   
27     for (int i = 1; i <= n; i ++ ) //枚举三角形底边终点的状态的最大值
28        res = max(res,f[n][i]);
29        
30     cout << res << endl;
31            
32     return 0;
33 }
View Code

 

标签:const,int,namespace,1e9,线性,dp
From: https://www.cnblogs.com/rw666/p/17844611.html

相关文章

  • MIT18.06Linear Algebra 第09讲 线性无关,基和维数
    转载于:超详细MIT线性代数公开课笔记......
  • Running DPDK Forwarding Applications With Pktgen-DPDK
    Aspartoftheevaluationstageofourbachelorthesis,wesetupatestbedforrunningforwardingapplicationsinDPDKandwithPktgen-DPDKasthetrafficgenerator.Inthisblog,weaimtocover作为学士论文评估阶段的一部分,我们建立了一个测试平台,用于在DPDK......
  • 线性代数导论MIT第二章知识点下
    2.3--2.7的知识点1.使用矩阵消元 2.消元矩阵 3.行交换矩阵 4.增广矩阵2.4矩阵运算规则 行与列方块矩阵与方块乘法舒尔补充2.5逆矩阵乘积AB的逆矩阵......
  • 2023 互测 R2T1 序列的线性做法
    把原题做法GF的系数进行OEIS,发现那个三角形就是Catalan数的GF复合上一个\(xy(1-x)\)的形式。更为奇妙的是,OEIS下面竟然给出了一个通项公式,\(T(n,k)=(-1)^{n-k}{k\choosen-k}C_k\),其中\(C\)是Catalan数列。代入原题的式子,发现答案竟然就是:\[\sum_{i=0}^n(-1)^{n......
  • 码-MDS线性码
    在码-综述中,我们讨论了SingletonBound,得出码字集合C中的码字的参数是(n,K,d),其中K ≤qn-d+1在线性码中,K= qk  ≤ qn-d+1,即有k ≤n-d+1 1.MDS线性码的定义C是参数为 [n,k,d] 的线性码且d=n-k+1,则称C为MDS线性码。 2.C的生成矩阵G,校验矩阵H,对偶码C⊥ ......
  • NEFU OJ Problem 1489 青蛙赶路 题解【动态规划DP】
    Problem:GTimeLimit:2000msMemoryLimit:65535KDescription有一只青蛙,每秒选择走1米或跳m米,青蛙体力不足,所以不能连续两秒都在跳。青蛙将移动到[l,r]之间,它想知道有多少种不同的方式来实现其目标。两种方式是不同的,当且仅当它们移动不同的米或花费不同的秒,或者是在一秒......
  • 码-线性码
    1.定义若C是Fqn的一个线性子空间,则称C是一个线性码。既然是线性子空间的话,一定有维数,例如C的维数是k,上一章引进的量中码字个数K=qk上一章引进的量中(n,K,d),  码字个数K,最小距离d现在引进线性码[n,k,d],码长n,码的维数k,最小距离d 2.线性码的最小距d(C)=mindH(x,y)=minW+(x-......
  • 线性回归的代码实现
    1.初始化步骤importnumpyasnpfromutils.featuresimportprepare_for_trainingclassLinearRegression:def__init__(self,data,labels,polynomial_degree=0,sinusoid_degree=0,normalize_data=True):"""初始化线性回归模型对象。......
  • 【DP】Leetcode 322 Coin Change
    题目链接322.零钱兑换思路因为硬币数量是无限的,所以无法以硬币数量作为状态进行遍历代码classSolution{publicintcoinChange(int[]coins,intamount){intn=coins.length;if(n==0){return-1;}//dp[i]......
  • Oracle expdp参数详解
    数据泵导出实用程序提供了一种用于在Oracle数据库之间传输数据对象的机制。该实用程序可以使用以下命令进行调用:示例:expdpscott/tigerDIRECTORY=dmpdirDUMPFILE=scott.dmp您可以控制导出的运行方式。具体方法是:在'expdp'命令后输入各种参数。要指定各参数,请使用......