天天看点

POJ 1976 A Mini Locomotive

题意:给出n车厢以及n节车厢内的人数 现有三节迷你火车头 每个火车头可以拉连续的m节车厢 问三个火车头最多可以拉多少人。

dp[i][j]表示第i节车厢有j个车头可以拉的总人数 dp[i][j]=max(dp[i-1][j],dp[k][j-1]+a[i]-a[k]) k=max(i-m,0) 前一个表示该节车厢不拉 后一状态表示加一个火车头拉

继续阅读