牛客周周练8
我果然是DP废物
昨天这题没什么思路,只会用DFS跑,但是30次不剪枝不记忆化肯定是不行了,早上看了一下别人题解,可以用dp来做。用dp[i][j]表示买i张彩票总共中了j元,最后统计方案数即可。
状态转移:
1 | for (int k = 1; k <= 4; k++) |
AC代码:
1 | ll dp[35][125]; |
看一下数据范围,一个很简单的DFS
AC代码:
1 | ll n; |
也是一个很简单的题,当一整行都为正数时,这一行的操作数就是该行的最小正数值。列同理。数据范围1000,$O(n^2)$没问题。
AC代码:
1 | ll mp[1005][1005]; |