UVA-624 CD

Uva 624 Cd

あなたは前方に車で長いドライブをしています。あなたはテープレコーダーを持っていますが、残念ながらあなたの最高の音楽はCDにあります。あなたはそれをテープに入れる必要があるので、解決する問題は次のとおりです：あなたはN分の長さのテープを持っています。 CDからトラックを選択して、テープスペースを最大限に活用し、未使用スペースをできるだけ短くする方法。仮定：

•CDのトラック数が20を超えない

•トラックがN分より長くない•トラックが繰り返されない

•各トラックの長さは整数で表されます

•Nも整数です

プログラムは、テープを最もよく埋めるトラックのセットを見つけて、トラックがCDに保存されているのと同じ順序で印刷する必要があります。

入力

任意の数の行。それぞれに値N、（スペースの後）トラック数とトラックの長さが含まれます。たとえば、サンプルデータの最初の行から：N = 5、トラック数= 3、最初のトラックは1分間、2番目のトラックは3分間、次のトラックは4分間続きます。

出力

正しいソリューションであるトラック（および期間）のセットと文字列「sum：」および期間時間の合計。

サンプル入力

5 3 1 3 4

10 4 9 8 4 2

20 4 10 5 7 4

90 8 10 23 1 2 3 4 5 7

45 8 4 10 44 43 12 9 8 2

サンプル出力

1から4：5 8 2 am 10

10 5 4合計：19

10 23 1 2 3 4 5 7合計：55

4 10 12 9 8 2合計：45

トピックの意味：保存時間nのブランクテープ、m曲から可能な限り数曲を選択し、ブランクスペースのブランク時間を最小にし、選択した曲を入力順に出力します。

問題解決のアイデア：0-1バックパック、2次元のdpがパスを記録するため、唯一の問題はパスの出力です。したがって、2次元のdpを使用して、最初の曲からdp [i] [j]を定義します。最初の曲へ曲を長くするために頭の数を選択してから、dp [i] [j] = max（dp [i-1] [j]、dp [i-1] [ja [i]] + a [i]）、次にパスを出力する方法は？

まず、dp配列を見つけるプロセスを見てみましょう。

For(int i=1i<=mi++)//Save song time from 1 { for(int j=0j<=nj++) { if(j

dp配列を最後から更新することです。dp[m] [n]の場合、最後の曲と最長時間dp [m] [n]が最後の変更であるため、データの最後の変更が必要です。 == dp [m-1] [na [m]] + a [m]は、最後の曲を選択する必要があることを意味します。これにより、最後の曲がans []配列に保存され、次にdp [m- 1] [ja [m]はそのステップからのものなので、パスを後ろから前に押すことができます。 ans []の導出は後ろから前であり、逆出力はOKであることに注意してください。これを理解します。この質問はちょうど終わりました。

ACコード：

#include #include #include #include using namespace std const int maxn=1e5 int a[22],dp[22][maxn],ans[22] int main() { int n,m while(cin>>n) { memset(dp,0,sizeof(dp)) cin>>m for(int i=1i>a[i] for(int i=1i<=mi++) { for(int j=0j<=nj++) { if(j0i--)// reverse output sequence { If(j-a[i]>=0&&dp[i][j]==dp[i-1][j-a[i]]+a[i])// indicates that the current i-th element is requested { ans[cnt++]=a[i] j-=a[i] } } For(int i=cnt-1i>=0i--)//The result is the direction, so it is output from the back to the front. { cout<