[SDOI2016]征途
大体
大概就是推推公式，发现很傻逼的(n^3)DP
get60
进一步我们发现状态不能入手，考虑优化转移
套个斜率优化板子
每一层转移来一次斜率优化
思路
先便便式子
[s^2=m^{2}*frac{sum_{1}^{m}(a_{i}-overline{a})^2}{m}
]
[=m*sum_{1}^{m}(a_{i}-overline{a})^2
]
[=m*sum_{1}^{m}(a_{i}^2-2*a_{i}*overline{a}+overline{a}^2)
]
[=m*sum_{1}^{m}a_{i}^2-m*sum_{1}^{m}2*a_{i}*overline{a}+m*sum_{1}^{m}overline{a}^2
]
[=m*sum_{1}^{m}a_{i}^2-m*sum_{1}^{m}2*a_{i}*overline{a}+m*sum_{1}^{m}overline{a}^2
]
[overline{a}^2=frac{sum_{1}^{m}a_{i}}{m}
]
[=m*sum_{1}^{m}a_{i}^2-m*sum_{1}^{m}2*a_{i}*frac{sum_{1}^{m}a_{i}}{m}+m*sum_{1}^{m}(frac{sum_{1}^{m}a_{i}}{m})^2
]
额，多化简化简，就得到了，LaTeX太麻烦了，这里就不多打了
[=m*sum_{1}^{m}a_{i}^2-2*(sum_{1}^{m}a_{i})^2+sum_{1}^{m}frac{(sum_{1}^{m}a_{i})^2}{m}
]
[=m*sum_{1}^{m}a_{i}^2-2*(sum_{1}^{m}a_{i})^2+(sum_{1}^{m}a_{i})^2
]
[=m*sum_{1}^{m}a_{i}^2-(sum_{1}^{m}a_{i})^2
]
注意:(sum_{1}^{m}a_{i}^2)和(2*(sum_{1}^{m}a_{i})^2)并不相同
然后我们发现(2*(sum_{1}^{m}a_{i})^2)是个定值
我们只需要求(sum_{1}^{m}a_{i}^2)这个最小就好了(m>0不用考虑)
然后我们可以(f[i][j])表示选了(i)次，到了第(j)个点的最小和（入门dp，无脑状态）
状态转移方程:
[f[i][j]=min(f[i][j],f[i-1][k]+(sum[j]-sum[k])*(sum[j]-sum[k]))
]
然后我们可以这个样纸
FOR(i,1,n) //选的第几次点
FOR(j,1,n) //位置
FOR(k,0,j) //由前面转移
f[i][j]=min(f[i][j],f[i-1][k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
我们发现状态是(n^2)个，每次转移是O(n)的，太墨迹了
那就套个斜率板子加个速，n次斜率转移
每一层都是由上一层转移，也可以滚动数组省内存一下，我看着128MB有点小
暴力60
/*
此题推出式子来就好办了，n^3dp直接斜率优化成n^2
次代码为本体暴力
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+7;
ll read() {
ll x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
ll n,m,sum[N];
ll f[3007][3007];
int main() {
n=read(),m=read();
for(int i=1;i<=n;++i) {
int x=read();
sum[i]=sum[i-1]+x;
}
memset(f,0x3f,sizeof(f));
for(int i=0;i<=n;++i) f[1][i]=sum[i]*sum[i];
for(int i=2;i<=m;++i) {
f[i][0]=0;
for(int j=1;j<=n;++j) {
for(int k=0;k<=j;++k) {
f[i][j]=min(f[i][j],f[i-1][k]+(sum[j]-sum[k])*(sum[j]-sum[k]));
}
}
}
cout<<m*f[m][n]-sum[n]*sum[n]<<"
";
return 0;
}
AC代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=3007;
ll read() {
ll x=0,f=1;char s=getchar();
for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
return x*f;
}
ll n,m,sum[N],f[N][N],q[N];
double calc(ll j,ll k,ll x) {
ll xx=sum[j];
ll yy=f[x-1][j]+sum[j]*sum[j];
ll xx_=sum[k];
ll yy_=f[x-1][k]+sum[k]*sum[k];
return (yy-yy_)/(2.0*(xx-xx_));
}
void work(int x) {
int h=0,d=0;
for(int i=1;i<=n;++i){
while(h<d && calc(q[h],q[h+1],x) <= sum[i]) h++;
f[x][i]=f[x-1][q[h]]+(sum[i]-sum[q[h]])*(sum[i]-sum[q[h]]);
while(h<d && calc(q[d],q[d-1],x) >= calc(q[d],i,x)) d--;
q[++d]=i;
}
}
int main() {
n=read(),m=read();
for(int i=1;i<=n;++i) {
int x=read();
sum[i]=sum[i-1]+x;
}
memset(f,0x3f,sizeof(f));
for(int i=0;i<=n;++i) f[1][i]=sum[i]*sum[i];
for(int i=2;i<=m;++i) {
f[i][0]=0;
work(i);
}
cout<<m*f[m][n]-sum[n]*sum[n]<<"
";
return 0;
}
wxy刷noi，而我等蒟蒻只能刷省选