E-Anya's Favorite CD(01滚动优化dp)
题目描述:
总共有t首歌,每次可以从该次的备选歌中选1首歌,总共选s首。问最少按多少次按钮。
备注:一开始从1开始播放,比如第一次要播放第3首歌,需要按两下按钮。
样例解释:
共15首歌,需要放两首,第一首可以在1、3、8、9里选一首放,第二首从12、2里选一首放。问最少按多少次按钮。
解题思路:
终于碰上一次01滚动优化的dp题了。计算一首歌切到另一首歌的时候需要按多少次按钮需要稍微考虑考虑。
代码:
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[2][1010]; ll now[1010]; ll old[1010]; ll comp(ll st, ll en, ll tks) { st = (st+1)%tks; ll r = st-en; if (r < 0) { r = -r; } ll ar = tks - r; if (r < ar) { return r; } return ar; } int main() { ll t, s, ans; ll oldsize = 1; ll nowsize; dp[0][0] = 0; old[0] = 0; scanf("%lld%lld",&t,&s); for(int i = 0; i < s; i++) { ans = -1; scanf("%lld",&nowsize); for(int j = 0; j < nowsize; j++) { scanf("%lld", &now[j]); dp[1][j] = -1; for(int k = 0; k < oldsize; k++) { ll tmp = comp(old[k], now[j], t) + dp[0][k]; if(dp[1][j] == -1 || tmp < dp[1][j]) { dp[1][j] = tmp; } } if(ans == -1 || ans > dp[1][j]) ans = dp[1][j]; } for(int j = 0; j < nowsize; j++) { old[j] = now[j]; dp[0][j] = dp[1][j]; } oldsize = nowsize; } printf("%lld\n",ans); }