题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4518
数据生成器:http://paste.ubuntu.com/23249800/
做过玩具装箱的童鞋,看一眼就知道是斜率DP吧?
#include<bits/stdc++.h> #define pow(x) ((x)*(x)) #define LL long long using namespace std; const int N = 3000+9; const LL INF = 1e16; LL f[N][N]; short n,m,l[N],sum,que[N][N],t1[N],t2[N]; double slope[N][N],Y[N][N]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } int main(){ n = read(); m = read(); for (int i=1;i<=n;i++) sum += (l[i] = read()), l[i] += l[i-1]; for (int i=0;i<m;i++) t1[i] = 1, f[n][i] = -1; t2[0] = 1; for (int i=1;i<=n;i++) for (int j=m-1;~j;j--) { if (t1[j]>t2[j]) continue; double tmp = 2.0*m*((double)m*l[i]-sum); while (t2[j] > t1[j] && slope[j][t1[j]] <= tmp) t1[j]++; f[i][j+1] = f[que[j][t1[j]]][j] + pow(sum-(LL)m*(l[i]-l[que[j][t1[j]]])); tmp = f[i][j+1] + pow((double)m*l[i]); while (t1[j+1] < t2[j+1] && ((tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]) <= slope[j+1][t2[j+1]-1])) t2[j+1]--; if (t1[j+1] <= t2[j+1]) slope[j+1][t2[j+1]] = (tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]); t2[j+1]++; que[j+1][t2[j+1]] = i; Y[j+1][t2[j+1]] = tmp; } LL vout = INF; for (int i=1;i<=m;i++) if (~f[n][i]) vout = min(vout,f[n][i]+(LL)(m-i)*pow(sum)); printf("%lld\n",vout/m); return 0; }
然而再zgs的OJ上莫名其妙RE了两个点?
奥妙重重……..
After study a few of the blog posts on your website now, and I truly like your way of blogging. I bookmarked it to my bookmark website list and will be checking back soon. Pls check out my web site as well and let me know what you think.
I?¦ve recently started a site, the information you offer on this site has helped me greatly. Thank you for all of your time & work.