HPU积分赛 Multivariate function ——————数学

末蓝、 2022-05-15 02:08 184阅读 0赞

# Multivariate function #

**描述**

*y*=*m**a**x*\{ *x**j*∗*x**p*−*x**i*∗*x**k**x**k*∗(*x**i*\+*x**j*)\}(0<*i*<*j*<*p*<*k*≤*n*)  y = m a x \{ x j ∗ x p − x i ∗ x k x k ∗ ( x i + x j ) \} ( 0 < i < j < p < k ≤ n )

**输入**

第一行一个整数T，表示T组测试数据 (1≤T≤10).  
每组数据第一行一个整数n (4≤n≤1000).  
第二行 n个浮点数: *x*1,*x*2...*x**n*  x 1 , x 2 . . . x n  (1≤x≤1000000).

**输入样例**

2  
4  
1.0 2.0 3.0 4.0  
5  
1.6 2.6 7.1 2.3 2.6

**输出样例**

0.167  
1.530

--------------------

一道学长出的数学题，

*y*=*m**a**x*\{ *x**j*∗*x**p*−*x**i*∗*x**k**x**k*∗(*x**i*\+*x**j*)\}(0<*i*<*j*<*p*<*k*≤*n*)  y = m a x \{ x j ∗ x p − x i ∗ x k x k ∗ ( x i + x j ) \} ( 0 < i < j < p < k ≤ n )

化简一下

*y*=*m**a**x*\{ *x**j*∗*x**p**x**k*∗(*x**i*\+*x**j*)−*x**i**x**i*\+*x**j*\}(0<*i*<*j*<*p*<*k*≤*n*)  y = m a x \{ x j ∗ x p x k ∗ ( x i + x j ) − x i x i + x j \} ( 0 < i < j < p < k ≤ n )

*y*=*m**a**x*\{ *x**p**x**k*∗*x**j**x**i*\+*x**j*−*x**i**x**i*\+*x**j*\}(0<*i*<*j*<*p*<*k*≤*n*)  y = m a x \{ x p x k ∗ x j x i + x j − x i x i + x j \} ( 0 < i < j < p < k ≤ n )

有没有看出来？有没有？

只需要找出来最大的*x**p**x**k*  x p x k   
然后再枚举 p 前边的 i , j 就好了

--------------------

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1e3+7;
    const double INF = 1.0*0x3f3f3f3f;
    int t,n;
    double a[MAXN],vis[MAXN],pre[MAXN];
    
    int main()
    {
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d",&n);
            for(int i=1;i<=n;i++)    scanf("%lf",&a[i]);
            for(int p=n-1;p>=1;p--)         //找到最大的x[p]/x[k]
            {
                double minn=INF;
                for(int k=p+1;k<=n;k++)
                    minn=min(minn,a[k]);
                vis[p]=a[p]/minn;
            }
            double maxx = -INF;
            for(int i=n-1;i>=1;i--)         //如果后边有更大的x[p]/x[k],就更新当前的值，将其变成大值
            {
                maxx=max(maxx,vis[i]);
                pre[i]=maxx;
            }
            double ans = -INF;
            for(int i=1;i<=n-3;i++)
                for(int j=i+1;j<=n-2;j++)
                    ans=max(ans,(a[j]*pre[j+1]-a[i])/(a[i]+a[j]));
            printf("%.3lf\n",ans);
        }
        return 0;
    }