hdu6546 Function

Function

\(\text{Alice}\) 有 \(n\) 个二次函数 \(F_i(x)=a_ix^2+b_ix+c_i(i \in [1,n])\)。

现在他想在 \(\sum_{i=1}^{n}{x_i=m}\) 且 \(x\) 为正整数的条件下求 \(\sum_{i=1}^n{F_i(x_i)}\) 的最小值。

请求出这个最小值。

Input

第一行两个正整数\(n，m。\)

下面\(n\)行，每行三个整数\(a，b，c，\)分别代表二次函数的二次项，一次项，常数项系数。

Output

一行一个整数表示答案。

Sample Input

2 3

1 1 1

2 2 2

Sample Output

13

Data range

对于全部测试数据满足：

\(a_i\in[1,10^3]\)

\(b_i,c_i\in[-10^3,10^3]\)

\(n\leq m\)

测试点编号	\(m\)
`1 ~ 2`	\(\leqslant 10\)
`3 ~ 4`	\(\leqslant 100\)
`5 ~ 6`	\(\leqslant 500\)
`7 ~ 10`	\(\leqslant 5 \times 10^3\)
`11 ~ 20`	\(\leqslant 10^5\)

思路：

先给每个函数的\(x\)赋为\(1\),再把\(f_i(x_i+1)-f_i(x_i)\)与\(i\)存入优先队列，按\(\Delta f_i\)进行\(x_i+1\)的操作\(,\)再把\(f_i(x_i+1)-f_i(x_i)\)与\(i\)塞回优先队列\(,\)重复\(m-n\)次

证明：

\(\because f^{'}_i(x)=2a_i+b_i\And a_i \geq 1\)

\(\therefore \Delta f_i\)随\(x_i+1\)操作单调增加

又\(\because\)要求\(\sum_{i=1}^nf_i(x_i)\)最小

\(\therefore\)最小的\(\Delta f_i\)一定要执行\(x_i+1\)操作

\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)

#include<cstdio>

#include<cmath>

#include<queue>

#include<iostream>

#include<algorithm>

using namespace std;

# define Type template<typename T>

# define read read1<ll>()

Type inline T read1()

{

    T t=0;

    char k;

    bool fl=0;

    do k=getchar(),(k=='-')&&(fl=1);while('0'>k||k>'9');

    while('0'<=k&&k<='9')t=(t<<3)+(t<<1)+(k^'0'),k=getchar();

    return fl?-t:t;

}

# define A pair<ll,int>

# define ll long long

priority_queue<A,vector<A>,greater<A> >q;

int s,nx[100001],m;

ll a[100001],b[100001],c[100001],ans;

ll f(ll x,int n){return a[n]*x*x+b[n]*x+c[n];}

int main()

{

    freopen("function.in","r",stdin);

    freopen("function.out","w",stdout);

    s=read;m=read-s;

    for(int i=0;i++^s;nx[i]=1)

    {

        a[i]=read,b[i]=read,c[i]=read;

        q.push(A(f(2,i)-f(1,i),i));

        ans+=f(1,i);

    }

    while(m--)

    {

        A tem=q.top();

        q.pop();

        ans+=tem.first;

        ++nx[tem.second];

        tem.first=f(nx[tem.second]+1,tem.second)-f(nx[tem.second],tem.second);

        q.push(tem);

    }

    printf("%lld\n",ans);

    return 0;

}

巴特西

hdu6546 Function

Function

Input

Output

Sample Input

Sample Output

Data range

最新文章

热门文章