USACO 3.4.4 Raucous Rockers 破锣摇滚乐队
一道动态规划题，但观察数据规模，穷举就行了。 穷举每首歌是否选取所有的组合可能(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