[洛谷U63006]导函数最小系数

2019-02-19 来源: water_lift 发布在  https://www.cnblogs.com/water-lift/p/10400724.html

U63006 导函数最小系数

题面

给出一个n次函数\(f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+...+a_{1}x+a_0\)的各项系数\(a_n,a_{n-1}...a_1,a_0\)
你的任务是求出它的导函数,然后从中删去k项,使得各项系数和最小。

格式

输入包括两行。
第一行包括一个整数\(n,k\)。
第二行n+1个整数\(a_n,a_{n-1}...a_1,a_0\)

输出包括一行,即所求的最小系数和。具体格式见样例

样例#1

输入

2 1
2 3 1

输出

3

解释

所求导函数为\(f(x)=4x+3\),删去4x后最优。

样例#2

输入

7 3
3 8 0 2 1 7 4 4

输出

15

解释

所求导函数为\(f(x)=21x^6+48x^5+8x^3+3x^2+14x+4\),删去\(21x^6,48x^5,14x\)后最优。

数据限制

规模 n k
50% \([1,20]\) \([0,n]\)
50% \([1,10000]\) \([0,n]\)
规模 \(a_i\)
20% \(0\)
80% \([-49,50]\)

分析

解法

#include<bits/stdc++.h>
using namespace std;
int n,k,a[10001];
int ans;
int main(){
    cin>>n>>k;
    for(int i=n;i>=0;i--){
        cin>>a[i];
        a[i]*=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n-k;i++){
        ans+=a[i];
    }
    cout<<ans<<endl;
} 

数据

相关文章