| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
wa大侠帮助下!#include <iostream>
#include <cstring>
#include <fstream>
#define in cin
using namespace std;
int h, n, f[26], d[26], t[25], best[26], current[26], bestnum, currentnum;
/*
将C前面路上的开销减去
*/
void roadtimecost ( int c )
{
for ( int i = 1; i < c; i ++ )
h -= 5 * t[i];
}
/*
C前面还有地方有鱼
*/
bool fishavailable ( int c )
{
bool flag = false;
for ( int i = 1; i <= c; i ++ )
if ( f[i] > current[i] * d[i] )
flag = true;
return flag;
}
void solve ( int i )
{
int j;
roadtimecost ( i );
while ( h > 0 && fishavailable ( i ) )
{
int max = -1, index = -1;
/*贪心选择一个可以获得最多鱼的*/
for ( j = 1; j <= i; j ++ )
if ( f[j] - current[j] * d[j] > max )
{
index = j;
max = f[j] - current[j] * d[j];
}
h -= 5;
current[index]++;
}
/*算出当前策略可以得到的鱼*/
for ( j = 1; j <= i; j ++ )
{
int temp = f[j];
for ( int k = 0; k < current[j]; k ++ )
{
if ( f[j] >= d[j] )
{
currentnum += f[j];
f[j] -= d[j];
}
else
currentnum += f[j];
}
f[j] = temp;
}
}
int main ()
{
ifstream in ( "1042.txt" );
int i, left;
bool flag = false;
while ( in >> n )
{
if ( n == 0 )
break;
in >> h;
h *= 60;
for ( i = 1; i <= n; i ++ )
in >> f[i];
for ( i = 1; i <= n; i ++ )
in >> d[i];
for ( i = 1; i < n; i ++ )
in >> t[i];
bestnum = 0;
for ( i = 1; i <= n; i ++ )
{
int th = h;
left = h;
currentnum = 0;
memset ( current, 0, sizeof ( current ) );
solve ( i );
if ( currentnum > bestnum )
{
memcpy ( best, current, sizeof ( current ) );
bestnum = currentnum;
for ( int k = 1; k < i; k ++ )
left -= t[k] * 5;
}
h = th;
}
if ( flag )
cout << endl;
for ( i = 1; i <= n; i ++ )
left -= best[i] * 5;
/*收获的鱼为0,那么将时间全部花在1那边*/
if ( bestnum == 0 )
{
for ( i = 1; i <= n; i ++ )
best[i] = 0;
left = h;
}
cout << best[1] * 5 + left;
for ( i = 2; i <= n; i ++ )
cout << ", " << best[i] * 5;
cout << endl;
cout << "Number of fish expected: " << bestnum << endl;
flag = true;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator