Task 7
Задача на динамическое программирование
#include <map> #include <iostream> #include <vector> using namespace std; #define MAX_SIZE 310 double P[MAX_SIZE][MAX_SIZE]; double p[MAX_SIZE][MAX_SIZE]; double sc[MAX_SIZE][MAX_SIZE] = {0.0}; int main( void ) { int N, K; double G[MAX_SIZE]; double W[MAX_SIZE]; double s = 0; int t; int d; freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); cin >> N >> K; for( int i = 0; i < N; i++) cin >> G[i] >> W[i]; for( int i = 0; i < N; i++) for( int j = 0; j < N; j++) cin >> P[i][j]; for( int i = 0; i < N; i++) for( int j = 0; j < N; j++) { if( P[i][j] == -1.0) p[i][j] = -1.0; else p[i][j] = G[j] - W[j]*P[i][j]; } for( int i = 0; i < N; i++) sc[0][i] = G[i]; for( int l = 1; l < K; l++) for( int i = 0; i < N; i++) { for( int j = 0; j < N; j++) { if( sc[l-1][j] == 0 ) continue; if( p[j][i] == -1.0) continue; sc[l][i] = max(sc[l][i], sc[l-1][j] + p[j][i]); } } for( int i = 0; i < N; i++) s = max(s,sc[K-1][i]); cout << s; return 0; }
page revision: 1, last edited: 18 Nov 2006 20:52