- #pragmacomment(linker, "/STACK:1024000000,1024000000")
- #include
- #include
- #include
- #include
- #include
- #include
- #include<set>
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- const doublepi=acos(-1.0),eps=1e-10;
- void File()
- {
- freopen("D:\\in.txt","r",stdin);
- freopen("D:\\out.txt","w",stdout);
- }
- template <classT>
- inline voidread(T &x)
- {
- charc = getchar();
- x =0;
- while(!isdigit(c)) c = getchar();
- while(isdigit(c))
- {
- x = x *10+ c -'0';
- c = getchar();
- }
- }
- int n,m;
- long longa[1005],sum[1005],p[1005][1005],dp[1005][1005];
- intf1,f2,q[2000];
- booldelete1(intx,inta,intb,int c)
- {
- if(dp[b][x]-p[1][b]+sum[b]*sum[b]-dp[a][x]+p[1][a]-sum[a]*sum[a]return 1;
- return 0;
- }
- booldelete2(intx,inta,intb,int c)
- {
- if((dp[c][x]-p[1][c]+sum[c]*sum[c]-dp[b][x]+p[1][b]-sum[b]*sum[b])*(sum[b]-sum[a])<
- (dp[b][x]-p[1][b]+sum[b]*sum[b]-dp[a][x]+p[1][a]-sum[a]*sum[a])*(sum[c]-sum[b]))return 1;
- return 0;
- }
- int main()
- {
- while(~scanf("%d%d",&n,&m))
- {
- if(n==0&&m==0)break; m++;
- for(inti=1;i<=n;i++)
- {
- scanf("%d",&a[i]);
- sum[i]=sum[i-1]+a[i];
- }
- for(inti=1;i<=n;i++)
- {
- for(intj=1;j<=n;j++)
- {
- ints=j,e=j+i-1;
- if(e>n)continue;
- if(i==1) { p[s][e]=0;continue; }
- p[s][e]=p[s+1][e]+a[s]*(sum[e]-sum[s]);
- }
- }
- for(inti=1;i<=n;i++) dp[i][1]=p[1][i];
- for(intj=2;j<=m;j++)
- {
- f1=0; f2=0; q[f2]=j-1;
- for(inti=j;i<=n;i++)
- {
- while(1)
- {
- if(f2-f1+1<2)break;
- if(delete1(j-1,q[f1],q[f1+1],i)) f1++;
- else break;
- }
- dp[i][j] = dp[q[f1]][j-1]+p[q[f1]+1][i];
- while(1)
- {
- if(f2-f1+1<2)break;
- if(delete2(j-1,q[f2-1],q[f2],i)) f2--;
- else break;
- }
- f2++; q[f2]=i;
- }
- }
- printf("%lld\n",dp[n][m]);
- }
- return 0;
- }
来源: