Home | Problems | Discuss | Login

  

no title

2818: QQ音速

imachang | 2017-09-03 21:56:43 | delete | edit
题解
这道题我们不难找到有三个状态:处理到第几个数字,以及处理这个数字时手的位置,以及
最低花费。
我们设dp[i][j][k]表示处理到第i个数时两个手指得按位。
对于第num个数字其中一个按位,我们可以得到:dp[i+1][num][j]=dp[i+1][j][num]=
min(dp[i+1][num][j],dp[i][j][k]+cost[k][num])
另外一个同理。
考虑到直接这样写会超内存,可以用滚动数组解决。
既是 dp[2][4][4] 

Please login to reply.