Description Pine開始了從S地到T地的征途。 從S地到T地的路可以劃分成n段，相鄰兩段路的分界點設有休息站。 Pine計劃用m天到達T地。除第m天外，每一天晚上Pine都必須在休息站過夜。所以，一段路必須在同一天中走完。 Pine希望每一天走的路長度儘可能相近，所以他希望每一天走的路的 ...
Submit: 1875 Solved: 1045
[Submit][Status][Discuss]
Description
Pine開始了從S地到T地的征途。 從S地到T地的路可以劃分成n段，相鄰兩段路的分界點設有休息站。 Pine計劃用m天到達T地。除第m天外，每一天晚上Pine都必須在休息站過夜。所以，一段路必須在同一天中走完。 Pine希望每一天走的路長度儘可能相近，所以他希望每一天走的路的長度的方差儘可能小。 幫助Pine求出最小方差是多少。 設方差是v，可以證明，v×m^2是一個整數。為了避免精度誤差，輸出結果時輸出v×m^2。Input
第一行兩個數 n、m。 第二行 n 個數，表示 n 段路的長度Output
一個數，最小方差乘以 m^2 後的值
Sample Input
5 21 2 5 8 6
Sample Output
36HINT
1≤n≤3000,保證從 S 到 T 的總路程不超過 30000
Source
其實這題並不是很難，只怪自己太垃圾 首先我們把題目中給出的式子拆開 然後暴力推，發現最終答案只與$v_i^2$有關，$v_i$為拆出來的每個區間的長度 這樣我們令$f[i][j]$表示前$i$個元素，選出了$j$段區間的最優方案 $$f[i][j]=min(f[i][j],\sum_{k=1}^{i-1} f[k][j-1])$$然後暴力推推推， 最終可以化簡為$$f[i][l]+2sum[i]sum[j]=f[j][l-1]+sum[j]^2$$ $sum[i]$為$i$的首碼和。 這樣的話就可以愉快的斜率優化啦 第二維可以用滾動數組滾動掉
// luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<bitset> #include<cmath> #include<algorithm> #define int long long //#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++) char buf[1<<23],*p1=buf,*p2=buf; using namespace std; const int MAXN=1e5+10; const int limit=100000; int N,M; int f[MAXN],g[MAXN]; int sum[MAXN]; int sqr(int x) {return x*x;} int Query(int l,int r){return sum[r]-sum[l-1];} int X(int x){return sum[x];} int Y(int x){return g[x]+sqr(sum[x]);} int slope(int x,int y){return (Y(y)-Y(x)) / (X(y)-X(x));} int Q[MAXN]; main() { #ifdef WIN32 freopen("a.in","r",stdin); //freopen("b.out","w",stdout); #endif scanf("%d%d",&N,&M); for(int i=1;i<=N;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1]; for(int i=1;i<=N;i++) g[i]=sqr(sum[i]); for(int k=1;k<=M-1;k++) { memset(f,0x3f,sizeof(f)); int h=1,t=1;Q[1]=k-1; for(int i=k+1;i<=N;i++) { while(h<t&&slope(Q[h],Q[h+1])<2*sum[i]) h++; int j=Q[h]; f[i]=min(f[i],g[j]+sqr(Query(j+1,i))); while(h<t&&slope(Q[t-1],Q[t])>slope(Q[t-1],i)) t--; Q[++t]=i; } memcpy(g,f,sizeof(f)); } printf("%lld",-sum[N]*sum[N]+f[N]*M); return 0; }
