这题的正解为dp
主体思路是:
建一个四维数组
dp[i][j][k][l]
用来存用i
张走一格的卡牌、用j
张走二格的卡牌、用k
张走三格的卡牌、用l
张走一格的卡牌时最多可以得到几分。然后四重循环,循环中建一个变量
x
,表示已经走了几步,注意起点的一步也要加上。之后如果
i==0&&j==0&&k==0&&l==0
,就把dp[i][j][k][l]
赋值为分数数组的第一项,否则
如果
i>=1
,dp[i][j][k][l]
就等于dp[i][j][k][l]和dp[i-1][j][k][l]+a[x]
之间的最大值如果
j>=1
,dp[i][j][k][l]
就等于dp[i][j][k][l]和dp[i][j-1][k][l]+a[x]
之间的最大值…
以此类推
最后输出dp的最后一项就好啦!
这样,一道水绿就过了。
核心代码
不给