排隊(duì)買票問(wèn)題PASCAL動(dòng)態(tài)規(guī)劃

一場(chǎng)演唱會(huì)即將舉行，現(xiàn)有n個(gè)歌迷排隊(duì)買票，一人面一張票，而售票處規(guī)定，一人每次只能買一張票，假設(shè)第i位歌迷買一張票需要時(shí)間T[i](1<=i<=n),隊(duì)伍中相鄰的兩位歌迷（第j個(gè)人和第j+1個(gè)人）也可以由其中一個(gè)人買兩張票，而另一個(gè)人就可以不用排隊(duì)了，則這兩位歌迷買兩張票的時(shí)間變?yōu)镽[j],且有R[j]

1個(gè)回答

2024-01-22 01:52

狀態(tài)轉(zhuǎn)移方程是 f[i] := min(f[i - 1] + t[i], f[i - 2] + r[i - 1]); {i = 2 ~ n}

初值 f[0] := 0; f[1] := t[1];

完整的代碼就不需要了吧?