APIO 2014 시퀀스 분할 bzoj3675
1735 단어 dp
이 문제는 분명히 Dp방정식 분정 f[i]=f[j]+s[j]*(s[i]-s[j])를 쓸 수 있다. 왜냐하면 이 문제는 실제적으로 자르는 순서와 무관하기 때문이다. 사실 이것은 답안의 모든 구간에 반드시 k를 곱한다는 것을 분명히 증명한다.차(대충 뇌를 보충해 보았지만 실제 계산이 없었다) 그리고 둥지들은 항상 기쁘게 경사율 최적화를 쓸 수 있었다
당시 경사율 DP 특집 경기 분노 AK의 RP 어디 갔어 QAQQQQQQQQQQQ
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100005
#define LL long long
using namespace std;
LL sum[N],f[N],q[N],a[N],g[N];
int n,k;
LL read()
{
LL x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
double calc(int j,int k)
{
return (double)(sum[k]*sum[k]-sum[j]*sum[j]-g[k]+g[j])/(double)(sum[k]-sum[j]);
}
void work(int x)
{
int h=1,t=0;
for (int i=x;i<=n;i++)
{
while (h<t&&calc(q[t-1],q[t])>calc(q[t],i-1)) t--;q[++t]=i-1;
while (h<t&&calc(q[h],q[h+1])<sum[i]) h++;int p=q[h];
f[i]=g[p]+(sum[i]-sum[p])*sum[p];
}
for (int i=x;i<=n;i++) swap(f[i],g[i]);
}
void dp()
{
for (int i=1;i<=k;i++)
work(i);
printf("%lld
",g[n]);
}
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++)
a[i]=read();
int top=0;
for(int i=1;i<=n;i++)
if(a[i]!=0)
a[++top]=a[i];
n=top;
for(int i=1;i<=n;i++)
sum[i]=sum[i-1]+a[i];
dp();
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【경쟁 프로 전형적인 90문】008의 해설(python)의 해설 기사입니다. 해설의 이미지를 봐도 모르는 (이해력이 부족한) 것이 많이 있었으므로, 나중에 다시 풀었을 때에 확인할 수 있도록 정리했습니다. ※순차적으로, 모든 문제의 해설 기사를 들어갈 예정입니다. 문자열...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
