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