\(Description\)
给定一个\(n\)个数的序列,最多将序列分为\(m+1\)段,每段的价值是这段中所有数两两相乘的和。求最小总价值。
\(Solution\)
写到这突然懒得写了。。
/*朴素O(n^3):f[i][j]表示当前在i分了j段的最小价值 W[i]表示1~i的总价值 S[i]表示1~i的原序列值之和 则有 f[i][j]=min{ f[k][j-1]+W[i]-W[k]-S[i]*(S[i]-S[k]) } (1≤k #include#define gc() getchar()typedef long long LL;const int N=1e3+5;int n,m,A[N],q[N];LL W[N],S[N],f[N][2];inline int read(){ int now=0,f=1;register char c=gc(); for(;!isdigit(c);c=gc()) if(c=='-') f=-1; for(;isdigit(c);now=now*10+c-'0',c=gc()); return now*f;}inline LL Calc_X(int x,int y){ return S[x]-S[y];}inline LL Calc_Y(int x,int y,int s){ return (f[x][s]+S[x]*S[x]-W[x])-(f[y][s]+S[y]*S[y]-W[y]);}inline LL Calc_f(int x,int y,int s){ return f[x][s]+W[y]-W[x]-S[x]*(S[y]-S[x]);}int main(){ while(n=read(),m=read(),n&&m) { S[0]=W[0]=0; for(int i=1;i<=n;++i) A[i]=read(), S[i]=S[i-1]+A[i], W[i]=W[i-1]+A[i]*S[i-1]; for(int i=1;i<=n;++i) f[i][0]=W[i]; int p=1; for(int h,t,j=1;j<=m;++j)//至多分m+1段 { h=t=1, q[1]=0;//i从0转移就是W[i] p^=1; for(int i=1;i<=n;++i) { while(h