题意

给定权值矩阵，需要从左上角走到右下角，只能往右或往下走且权值会累加，问至少需要提前准备多少权值才能保证过程中不出现权值被耗尽的情况。

Solution

正着不太好写，可以尝试倒过来dp，$dp[i][j]$ 表示当前位置到终点至少需要准备多少权值，这样每个点要么从下边转移，要么从右边转移，选择最小的那个点转移即可，过程中需要保证权值至少为1，得到转移方程：$dp[i][j] = max(min(dp[i+1][j],dp[i][j+1])-mp[i][j],1)$。

题意

一共12道题，你有 $a_i$ 的概率做对第 $i$ 题，有 $b_i$ 的概率抄到左边的，有 $c_i$ 的概率抄到右边的，问做对 $0-12$ 题的概率是多少。

solution

做对的概率不太好求，可以反过来求做错的概率，即 $(1-a[i])\times(1-b[i])\times(1-c[i])$，然后 $dp[i][j]$ 表示前 $i$ 道题做对 $j$ 道的概率，设 $dp[0][0] =1$，得到状态转移方程：$dp[i][j]=dp[i-1][j-1]\times(ac=(1-wa))+dp[i-1][j]*wa$ 。

题意：

桥长度为$L$ ，分布有$n$ 个石子，青蛙每次可以跳 $[S,T]$ 的距离,问青蛙过桥至少要踩多少个石子。

$(1<=S,T<=10,m<=100,a_i<=10^9, a_i 表示第i个石子的位置)$

solution

题意

$n$ 件食材（每种食材的数量可以视为无限），小明连续工作 $T$ 时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第 $i$ 道菜肴有三个属性 $ai$，$bi$，$ci$，$ai$ 是该菜肴的美味值，$bi$ 是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：$ai-t*bi$，完成这道菜需要 $ci$ 的时间。求在这 $T$ 时间内能做出菜肴使得总美味值的最大值。

solution

首先需要贪心确定顺序，考虑只有两道菜，可以得到：$a_i−b_i∗c_i+(a_j−b_j∗(c_i+c_j))>=a_j−b_j∗c_j+(a_i−b_i∗(c_i+c_j))$，化简后得到：$b_i∗c_i>=b_j∗c_i$。排序后背包即可（需要降维）。