arrow_upward

标签-动态规划

首先预处理一下两个单词 $s[i],s[j]$ 是否安全并记录在 $can[i][j]$ 中,用 $f[i]$ 代表包含第 $i$ 个单词的安全组有多少个。枚举每一个小于当前单词的单词,如果他们俩安全,那么当前单词和 枚举单词所在的安全组成员 在一起也一定是安全的,所以加上答案即可。$$f[j]= \begin{cases} f[j] \\ f[j]+f[i] , can[i][j] \&a...
   题解    0 条评论
提高+/省选-
显然用dp,用 $f[i]$ 表示前 $i$ 辆车过桥的最短时间,枚举上一个分组的最后一辆车 $j$ 进行转移,方程式为:$$f[i]=min \begin{cases} f[i] \\ f[j-1]+len\div s[i] \times 60 & j<=i, \sum ^{i}_{k=j}w[k]<=wmax \end{cases}$$其中 $tmax$ 是这一组中最...
   题解    0 条评论
普及+/提高
就是一道区间dp+高精,最开始还想拿int_128来水水的,结果算算还是不太够,就老老实实写了高精。$f[st][ed][cnt]$ 表示在区间 $st..ed$ 放 $cnt$ 个乘号的最大值,转移方程式为:$$f[st][ed][cnt]=\max \{ f[st][mid][x]\times f[mid+1][ed][cnt-x-1] \}$$每次转移时枚举放乘号的位置 $(mid)$...
   题解    0 条评论
普及/提高-
晚上做了洛谷TG试炼场的DP lv1 模块,还是大致总结一下。洛谷P1005 矩阵取数游戏区间DP。对于每行,我们可以单独处理。用 $ f[l][r] $ 表示已经取了 $ l..r $ 这个区间后的得分最大值。然后记忆化搜索即可。$ $ 肯定是爆long long了,按理来说应该要写高精的,但是我发现这玩意写高精如果没有运算符重载版的是真的恶心,然后__int128水过去了。#includ...
   题解    0 条评论
很久没写过总结了。紫书做了那么多道题,但是我的动规并没有找到什么感觉,也就只有普及难度的可以不看题解写,剩下的都是看着题解写完的,我还是太弱了。这里还是来总结一下吧。例题9-1 UVa1025-A Spy in the Metro$f[i][j]$表示在车站i,时刻是j,还剩多少时间(根紫书略有不同)决策有三个,上左边的车,上右边的车,如果都不开往幼儿园就等一时刻的车。注意还要判断某一时刻是...
   题解    0 条评论