这题很明显的是DP，DP方程很容易就想到为dp[i,j]=min(dp[k][j-1]+(sum[i]-sum[k])*g[j]）（n-b<=k<n-a)
但普通转移必定挂。
如果把方程变一变dp[i,j]=sum[i]*g[j]+min(dp[k][j-1]-sum[k]*g[j])
这样在如果j不变的情况下，后面的最小值是不变的。因此可以O(1)的转移
但由于存在范围，因此可以利用堆或者单调队列来处理
1 #include<stdio.h>
2 #include<iostream>
3 #include<string>
4 #include<vector>
5 #include<map>
6 #include<queue>
7 #include<algorithm>
8 #define M 1000
9 #define clr(x) memset(x,0,sizeof(x))
10 #define _clr(x) memset(x,-1,sizeof(x))
11 #define fr(i,a,b) for( i=a;i<b;++i)
12 #define pf printf
13 #define sf scanf
14 #define pb push_back
15 #define mp make_pair
16 #define ll long long
17 #define debug 1
18 using namespace std;
19 const ll oo=100000000000000ll;
20 ll dp[205][10005];
21 int x[11000],g[210];
22 ll sum[11000];
23 ll L;
24 int n,k,A,B;
25 inline
26 ll sqr(ll x)
27 {
28 return (ll)x*x;
29 }
30 void init()
31 {
32 int i;
33 L=0;
34 fr(i,1,n+1)
35 {
36 L+=x[i];
37 }
38 L=L/n;
39 sum[0]=0;
40 fr(i,1,n+1)
41 {
42 sum[i]=sum[i-1]+sqr(x[i]-L);
43 }
44 }
45 int l,r;
46 struct node
47 {
48 ll t;
49 int pos;
50 node(){}
51 node(ll t,int pos):t(t),pos(pos){}
52 };
53 int operator <(const node &a,const node&b)
54 {
55 return a.t<b.t||a.t==b.t&&a.pos<b.pos;
56 }
57 const int queuesize=10005;
58 node q[queuesize];
59 inline
60 ll min(ll a,ll b)
61 {
62 return a<b?a:b;
63 }
64 void sol()
65 {
66 int i,j;
67 fr(i,0,k+1)
68 {
69 fr(j,0,n+1)
70 dp[i][j]=oo;
71 }
72 dp[0][0]=0;
73 ll ans=-1;
74 int cl=k+1,T=n+1;
75 fr(i,1,k+1)
76 {
77 l=0,r=0;
78 fr(j,A,n+1)
79 {
80 if(dp[i-1][j-A]!=oo)
81 {
82 node tem=node(dp[i-1][j-A]-sum[j-A]*g[i],j-A);
83 while(l<r&&q[r-1].t>=tem.t)--r;
84 q[r++]=tem;
85 }
86
87 while(l<r&&q[l].pos<j-B)++l;
88 if(l==r)continue;
89 dp[i][j]=q[l].t+sum[j]*g[i];
90 }
91 if(dp[i][n]!=oo)
92 {
93 if(ans==-1||ans>dp[i][n])
94 {
95 ans=dp[i][n];
96 cl=i;
97 T=n-q[l].pos;
98 }
99 }
100 }
101 if(ans!=-1)
102 pf("%lld %d %d\n",ans,cl,T);
103 else
104 pf("No solution.\n");
105 }
106 int main()
107 {
108 freopen("in.txt","r",stdin);
109 int i;
110 int ca=0;
111 while(sf("%d%d%d%d",&n,&k,&A,&B)>0)
112 {
113 //if(ca++)pf("\n");
114 fr(i,1,n+1)
115 {
116 sf("%d",&x[i]);
117 }
118 fr(i,1,k+1)
119 {
120 sf("%d",&g[i]);
121 }
122 init();
123 sol();
124 }
125 return 0;
126 }
127