USACO 3.4.4 Raucous Rockers 破鑼搖滾樂隊
本文正體字版由OpenCC轉換
一道動態規劃題，但觀察數據規模，窮舉就行了。 窮舉每首歌是否選取所有的組合可能(2^20種)，算出每種情況所有光盤上一共能存的歌曲數目，保留最大值即可。
對於窮舉每首歌是否選取所有的組合可能，我採用了位運算的高效方法
limit=(1 << N)-1;
for (i=0;i<=limit;i++)
然後i對應的每種狀況計算能裝進光盤中的最大的歌曲數目即可。
USER: CmYkRgB CmYkRgB [cmykrgb1] TASK: rockers LANG: C++
Compiling… Compile: OK
Executing… Test 1: TEST OK [0.000 secs, 2844 KB] Test 2: TEST OK [0.000 secs, 2840 KB] Test 3: TEST OK [0.011 secs, 2840 KB] Test 4: TEST OK [0.000 secs, 2844 KB] Test 5: TEST OK [0.011 secs, 2844 KB] Test 6: TEST OK [0.011 secs, 2840 KB] Test 7: TEST OK [0.410 secs, 2840 KB] Test 8: TEST OK [0.454 secs, 2840 KB] Test 9: TEST OK [0.097 secs, 2844 KB] Test 10: TEST OK [0.000 secs, 2840 KB] Test 11: TEST OK [0.421 secs, 2844 KB] Test 12: TEST OK [0.454 secs, 2840 KB]
All tests OK.
/*
ID: cmykrgb1
PROG: rockers
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 21
using namespace std;
ifstream fi("rockers.in");
ofstream fo("rockers.out");
long N,T,M,maxr=0;
long len[MAX];
void init()
{
long i;
fi >> N >> T >> M;
for (i=1;i<=N;i++)
fi >> len[i];
}
void comser()
{
unsigned long limit,i;
long j,k,rec,st;
bool A;
long use[MAX];
limit=(1 << N)-1;
for (i=0;i<=limit;i++)
{
memset(use,0,sizeof(use));
rec=0;st=1;
for (j=1;j<=N;j++)
{
A=(i & (1 << (j-1))) >> (j-1);
if (A) for (k=st;k<=M;k++)
if (use[k]+len[j]<=T)
{
use[k]+=len[j];
rec++;
st=k;
break;
}
}
if (rec>maxr) maxr=rec;
}
}
void print()
{
fo << maxr << endl;
fi.close();
fo.close();
}
int main()
{
init();
comser();
print();
return 0;
}
上次修改時間 2017-02-03