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;
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.