其实打代码的感觉有点像网络流，重点是推导，剩下就是个板子。
总结一下算法流程
-
先推出一般形式 dp[i]=dp[j]+xxxx
-
展开移项
- 定义只有i的为b（这样求出b就相当于求dp[i]）
- 定义只有j的为y（是定点）
- 对于有i,j的为j项为x，i项为a
现在（x,y）(i之前的)就定下来了
现在维护一个凸包
若q[h]和q[h+1]的斜率比当前a小了，那q[h]就没用了
还有对于队尾的判断，如果q[i]和q[tail]的斜率比q[tail]和q[tail-1]小，那么对于tail也没用武之地了
最后对于状态i的最优策略点j就是q[h]了，O1跟新即可
Updated 2020/09/13
感觉之前写的太片面和肤浅了，这里补一发关于依据单调性的不同做法。
- x,k都是单调的，那么可以方便的直接维护凸包，同时因为凸包斜率单#调，所以决策也有单调性。可以在总复杂度O(n)下解决问题
- 只有x单调，依然可以建出凸包，但是决策不满足单调性，可以在凸包上二分最佳位置。时间复杂度：O(nlogn)
- x,k都不满足单调性，一种方法是建平衡树（博主懒，不想学也不想敲），另一种方法是cdq强制构造x,k的单调性。
流程如下：
-
所有点按照k排序
-
按照id划分为前一半后一半（注意此时仍然满足k的单调）
-
完成左半边计算，同时左半边结束时经过按照x的归并排序，没了k的单调性，多了x的单调性。
-
对左边单调的x建立凸包，然后对右边单调的k进行有决策单调性性质的查寻。
-
更新dp函数，最后按照x归并排序。
时间复杂度为优秀的O(nlogn)
关于斜率优化实现 算斜率的时候防止出现除数是0的情况，手动判断如果为0，返回inf or −inf。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,l,q[50005];
double s[50005],dp[50005];
double a(int i){return s[i]+i;}
double b(int i){return a(i)+l+1;}
double x(int i){return b(i);}
double y(int i){return dp[i]+b(i)*b(i);}
double k(int i,int j){return (y(i)-y(j))/(x(i)-x(j));}
signed main()
{
cin>>n>>l;
for(int i=1;i<=n;i++)
{
scanf("%lf",&s[i]);
s[i]+=s[i-1];
}
int h=1,t=1;
for(int i=1;i<=n;i++)
{
while(h<t&&k(q[h],q[h+1])<2*a(i)) h++;
dp[i]=dp[q[h]]+(a(i)-b(q[h]))*(a(i)-b(q[h]));
while(h<t&&k(q[t],i)<k(q[t-1],q[t])) t--;
q[++t]=i;
}
cout<<(int)dp[n]<<endl;
return 0;
}
|
写出dp方程式，然后能拆就拆，使得式子的x,y都是dp转折点，然后观察斜率的单调性维护即可。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include<bits/stdc++.h>
using namespace std;
#define int long long
const int M=4e6+50000;
int n,m,f[M],q[M],cnt[M],sum[M],a[M],mx;
inline double getangle(int x,int y){
return (double)(f[y]+sum[y]-f[x]-sum[x])/(cnt[y]-cnt[x]==0?1e-9:cnt[y]-cnt[x]);
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),cnt[a[i]]++,sum[a[i]]+=a[i],mx=max(mx,a[i]);
for(int i=0;i<=mx+m+1;i++){
cnt[i]+=cnt[i-1];sum[i]+=sum[i-1];
}
int h=1,t=0;
for(int i=0;i<=mx+m+1;i++){
f[i]=(cnt[i])*i-sum[i];
if(i-m>=0){
while(h<t&&getangle(q[t-1],q[t])>=getangle(q[t-1],i-m)) t--;
q[++t]=i-m;
}
while(h<t&&getangle(q[h],q[h+1])<=i) h++;
int j=q[h];
if(h<=t) f[i]=min(f[i],f[j]+(cnt[i]-cnt[j])*i-(sum[i]-sum[j]));
}
int ans=1e18;
for(int i=mx;i<=mx+m;i++) ans=min(ans,f[i]);
cout<<ans<<endl;
return 0;
}
|
考虑dp，排序后，题意抽象为将序列划分为m个区间，每个区间要干掉一个数，显然有如下O(N3)dp。
1
2
3
4
5
6
7
8
| sort(a+1,a+n+1);
for(int i=0;i<=n;i++) dp[i][0]=0;
for register int i=1;i<=n;i++)
for(register int j=1;j<=m;j++)
for(register int k=1;k<=i;k++){
dp[i][j]=min(dp[i][j],dp[k-1][j-1]+(i-k+1)*a[k]);
}
cout<<dp[n][m]<<"\n";
|
注意到dp方程式可以拆分，可以按照斜率优化套路。
题解给出另一种更通用的方法，比较相邻决策点什么时候更优，
a[k]−a[k′]f(k)−f(k′)<=−(i+1)
其中f(x)是简单变换。
于是答案一定在凸包上，然后在凸包上尺取即可。
时间复杂度O(nm)
但是细节有点多，我选择了简单的二分找最佳点。
时间复杂度O(nmlogn)，可过。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
using namespace std;
#define int long long
inline int getint(){
int summ=0,f=1;char ch;
for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
if(ch=='-')f=-1,ch=getchar();
for(;isdigit(ch);ch=getchar()) summ=(summ<<3)+(summ<<1)+ch-48;
return summ*f;
}
const int M=2005;
int dp[M][M],a[M],n,m,tp;
struct point{
int x,y;
point(int _x=0,int _y=0){
x=_x;y=_y;
}
point operator - (point b){
return point(x-b.x,y-b.y);
}
int operator ^ (point b){
return x*b.y-y*b.x;
}
}sta[M];
void Pre(){
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
dp[i][j]=1e18;
}
inline void Addpoint(point p){
while(tp>1&&((sta[tp]-sta[tp-1])^(p-sta[tp]))<=0) tp--;
sta[++tp]=p;
}
signed main(){
int T;cin>>T;
while(T--){
cin>>n>>m;
Pre();
for(int i=1;i<=n;i++) a[i]=getint();
sort(a+1,a+n+1);
for(int i=0;i<=n;i++) dp[0][i]=0;
for(int i=1;i<=m;i++){
tp=0;
for(int j=i;j<=n;j++){
Addpoint(point(a[j],-a[j]*j+dp[i-1][j-1]));
int res=1,l=1,r=tp;
while(l<=r){
if(r-l<=1){
if((point(sta[r]-sta[r-1])^point(1,-j-1))>=0) res=r;
else res=l;
break;
}
int mid=l+r>>1;
if((point(sta[mid]-sta[mid-1])^point(1,-j-1))>=0) l=mid;
else r=mid;
}
dp[i][j]=sta[res].y+sta[res].x*(j+1);
}
}
cout<<dp[m][n]<<"\n";
}
return 0;
}
|
题目告诉了我们一定存在最优解满足每次操作都必须卖光或者买光。
于是可以写出dp方程。
使用cdq消除问题。
code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include<bits/stdc++.h>
using namespace std;
#define double long double
const int M=2e5+5;
const double inf=1e15,eps=1e-18;
double A[M],B[M],R[M],s,f[M];
struct node{
double x,y,k;int id;
friend bool operator < (node x,node y){return x.k>y.k;}
}q[M],b[M],tmp[M];
int n,m,sta[M];
double X(int i){return R[i]*f[i]/(A[i]*R[i]+B[i]);}
double Y(int i){return f[i]/(A[i]*R[i]+B[i]);}
double Getk(int i,int j){
if(fabs(q[i].x-q[j].x)<eps) return inf;
return (q[j].y-q[i].y)/(q[j].x-q[i].x);
}
void cdq(int l,int r){
if(l==r){
f[l]=max(f[l],f[l-1]);q[l].x=X(l);q[l].y=Y(l);return;
}
int mid=l+r>>1,p=l-1,qq=mid;
for(int i=l;i<=r;i++) if(q[i].id<=mid) b[++p]=q[i];else b[++qq]=q[i];
for(int i=l;i<=r;i++) q[i]=b[i];
cdq(l,mid);
int h=1,t=0;
for(int i=l;i<=mid;i++){
while(h<t&&Getk(sta[t-1],sta[t])<Getk(sta[t-1],i)) t--;
sta[++t]=i;
}
for(int i=mid+1;i<=r;i++){
while(h<t&&Getk(sta[h],sta[h+1])>q[i].k) h++;
f[q[i].id]=max(f[q[i].id],A[q[i].id]*q[sta[h]].x+B[q[i].id]*q[sta[h]].y);
}
cdq(mid+1,r);
int l1=l,l2=mid+1,now=l-1;
while(l1<=p||l2<=qq){
if(l1==p+1){
tmp[++now]=q[l2];l2++;continue;
}
if(l2==qq+1){
tmp[++now]=q[l1];l1++;continue;
}
if(q[l1].x<q[l2].x){
tmp[++now]=q[l1];l1++;
}
else{
tmp[++now]=q[l2];l2++;
}
}
for(int i=l;i<=r;i++) q[i]=tmp[i];
}
int main(){
cin>>n>>s;
for(int i=1;i<=n;i++){
scanf("%Lf%Lf%Lf",&A[i],&B[i],&R[i]);
q[i].id=i;q[i].k=-(A[i]/B[i]);
}
sort(q+1,q+n+1);
f[0]=s;cdq(1,n);
printf("%0.5Lf",f[n]);
return 0;
}
|
