柒葉灬 的博客

柒葉灬 的博客

动态DP

posted on 2019-11-06 09:53:59 | under 算法学习 |

动态DP


一般的矩阵乘法:

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        for(int k=0;k<n;k++)
            c[i][j]+=a[i][k]*b[k][j];

广义矩阵乘法:

for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
        for(int k=0;k<n;k++)
            tomax(c[i][j],a[i][k]+b[k][j]);

这样矩阵乘法就可以适用于取max的题目了。

例如noip2018 D2T3