hdu6546 Function
Function
\(\text{Alice}\)\(n\)개의 2차 함수가 있습니다\(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,\)는 각각 2차 함수의 2차 항, 1차 항, 상수 항 계수를 대표한다.
Output
한 줄에 한 정수씩 답을 표시한다.
Sample Input
2 3 1 1 1 2 2 2
Sample Output
십삼
Data range
모든 테스트 데이터 충족:
테스트 포인트 번호
\(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
#include
#include
#include
#include
using namespace std;
# define Type template
# define read read1()
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
# define ll long long
priority_queue,greater>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",ans);
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
