链接:hdu1300
题解
- 其实这个数据量根本不需要优化2333
- dp[i]表示前i个数得到的最大价值
- 然后很容易就可以得到转移方程,每次选j~i这个级别的放在一起
- dp[i]=min(dp[j-1]+(sum[i]-sum[j-1])*p[i])
- 虽然到这里就可以AC了,还是考虑下斜率优化
- 考虑k<j,j比k更优
- 最后…数据有bug,排序会wa(或许是std挂了?逃)
dp
1 |
|
斜率优化
1 |
|
learn
链接:hdu1300
- 其实这个数据量根本不需要优化2333
- dp[i]表示前i个数得到的最大价值
- 然后很容易就可以得到转移方程,每次选j~i这个级别的放在一起
- dp[i]=min(dp[j-1]+(sum[i]-sum[j-1])*p[i])
- 虽然到这里就可以AC了,还是考虑下斜率优化
- 考虑k<j,j比k更优
- 最后…数据有bug,排序会wa(或许是std挂了?逃)
1 |
|
1 |
|