首页 > 代码库 > 123

123

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;
#define N 1001000

struct node {
    int b,d;
    double rate;
}g[N];

double dp[1001000];

int cmp(node n1, node n2) {
    return n1.b < n2.b;
}

/*请完成下面这个函数,实现题目要求的功能*/
/*当然,你也可以不按照下面这个模板来作答,完全按照自己的想法来 ^-^ */
/******************************开始写代码******************************/
double StockGod(int n, int m, double p, const vector<vector<double>>& prices)
{
    if (m == 1) {
        return 1;
    }
    int cnt = 0;
    
    for (int i = 0; i < n; i++) {
        
        int b = -1, d = -1;
        int j = 0;
        while (j < m - 1) {
            while (j + 1 < m && prices[j][i] >= prices[j + 1][i]) {
                j++;
            }
            b = j;
            while (j + 1 < m && prices[j][i] <= prices[j + 1][i]) {
                j++;
            }
            d = j;
            for (int ii = b;ii < d; ii++) {
                for (int jj = ii + 1;jj<=d;jj++) {
                    int tb = ii;
                    int td = jj;
                    double dis = prices[td][i] - prices[tb][j];
                    if (dis > 0) {
                        double mm = prices[td][i] * (1 - p) / prices[tb][i];
                        if (mm > 1) {
                            node nn;
                            nn.b = tb;
                            nn.d = td;
                            nn.rate = mm;
                            g[cnt++] = nn;
                        }
                    }
                }
            }
        }
    }
    
    sort(g, g + cnt, cmp);
    dp[0] = 1;
    double mx = 1;
    int ti = 0;
    for (int i = 0; i < m;i ++) {
        mx = max(dp[i], mx);
        while (ti < cnt && i == g[ti].b) {
            int d= g[ti].d;
            dp[d] = max(dp[d], mx * g[ti].rate);
            ti++;
        }
    }
    
    return mx;
}
/******************************结束写代码******************************/


int main()
{
    int n = 0;
    int m = 0;
    double p = 0;
    cin >> n >> m >> p;
    
    vector<vector<double>> prices;
    for(int i = 0; i < m; ++i) {
        prices.push_back(vector<double>());
        for(int j = 0; j < n; ++j) {
            double x = 0;
            cin >> x;
            prices.back().push_back(x);
        }
    }
    
    double final = StockGod(n, m, p, prices);
    printf("%.1f\n", final);
    
    return 0;
}

/**
 
**/

 

123