目录
0x5A~0x5B
0x5A 斜率优化
之前已经写过一些不再写一遍了。
0x5B 四边形不等式
a.[√]诗人小G
sol:
首先直接设出状态：\(f[i]\)表示前i首诗排版后的最小答案。
那么转移为：
\[
f[i]=min_{0≤j<i}\{f[j]+|sum[i]-sum[j]+i-j-1-L|^P\}
\]
由于存在高次，不符合单调队列优化和斜率优化，考虑四边形不等式优化。
令\(val(j,i)=|sum[i]-sum[j]+i-j-1-L|^P\)，
因为存在\(j<i\)，那么只需证明\(val(j,i+1)+val(j+1,i)≥val(j,i)+val(j+1,i+1)\)，
也即证明\(val(j+1,i)-val(j+1,i+1)≥val(j,i)-val(j,i+1)\)。
令\(a=(sum[i]+i)-(sum[j]+j)-(L+1),b=(sum[i]+i)-(sum[j+!]+j+1)-(L+1)\)
则只需证明：\(|a|^P-|a+(s[i+1]+1)|^P≥|b|^P-|b+(s[i+1]+1)|^P\)
由于\(a<b\)，所以等价于只要证明函数\(y=|x|^P-|x+c|^P\ (c为常数)\)单调递减，分类讨论求导可证。
所以就可以套决策单调性的板子了。
code:
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB long double
using namespace std;
IL int gi() {
RG int x=0,w=0; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return w?-x:x;
}
const int N=1e5+3;
char ch[N][33];
int n,h,t,L,P,a[N],s[N];
DB f[N];
struct rec{int x,l,r;}q[N];
IL DB qpow(int x,int p) {
RG DB a=x,ans=1.0;
for(;p;p>>=1,a=a*a)
if(p&1) ans=ans*a;
return ans;
}
IL DB calc(int i,int j) {return f[j]+qpow(abs(s[i]-s[j]+i-j-1-L),P);}
IL int search(int i) {
RG int l=q[t].l,r=q[t].r,mid;
while(l<r) {
mid=l+r>>1;
if(calc(mid,i)<=calc(mid,q[t].x)) r=mid;
else l=mid+1;
}
return r;
}
IL void print(int i) {
if(!i) return;
print(a[i]);
for(RG int j=a[i]+1;j<=i;++j) {
printf("%s",ch[j]);
if(j!=i) putchar(' ');
}
putchar('\n');
}
int main()
{
RG int i,T=gi();
while(T--) {
n=gi(),L=gi(),P=gi();
for(i=1;i<=n;++i)
scanf("%s",ch[i]),s[i]=s[i-1]+strlen(ch[i]);
h=1,t=0,q[++t]=(rec){0,1,n};
for(i=1;i<=n;++i) {
if(h<=t) {
if(q[h].r==i-1) ++h;
else q[h].l=i;
}
f[i]=calc(i,q[h].x),a[i]=q[h].x;
RG int pos=n+1;
while(h<=t) {
if(calc(q[t].l,i)<=calc(q[t].l,q[t].x)) pos=q[t--].l;
else {
if(calc(q[t].r,i)<=calc(q[t].r,q[t].x))
pos=search(i),q[t].r=pos-1;
break;
}
}
if(pos<=n) q[++t]=(rec){i,pos,n};
// 决策i是pos～n的最优决策
}
if(f[n]>1e18) puts("Too hard to arrange");
else printf("%lld\n",(LL)f[n]),print(n);
puts("--------------------");
}
return 0;
}b.[√] 合并石子
sol:
\(O(n^3)\)的很熟悉了，直接写：
\[
f[i,j]=\min_{i≤k<j}{}\{f[i,k]+f[k+1,j]\}+\sum_{k=i}^jA[k]
\]
打表发现其具有决策单调性（不会证明），则可以使复杂度降为\(O(n^2)\)。
值得一提的是：
3方DP中i是倒序枚举的，j是正序枚举的，则利用到的是：
\(p[i,j-1]≤p[i,j]≤p[i+1,j]\ (p[x,y]代表状态(x,y)的最优决策)\)
而对于其他可以用决策单调性优化的转移，若原始转移中i是正序枚举，j是倒序枚举，则有：
\(p[i-1,j]≤p[i,j]≤p[i,j+1]\ (p[x,y]代表状态(x,y)的最优决策)\)
应该只要符合决策单调性，就能套上这两种情况中的一种。
另外Luogu上的这题还有最大值要求，但最大值不满足决策单调性，但是它却必然是如下转移得到最优：
\(g[i,j]=max\{g[i,j-1],a[i+1,j]\}+\sum_{k=i}^jA[k]\) 原理应是贪心。
code:
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;
IL int gi() {
RG int x=0,w=0; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return w?-x:x;
}
const int N=903;
int n,ans1,ans2,a[N],s[N],f[N][N],g[N][N],pf[N][N],pg[N][N];
int main()
{
RG int i,j,k;
memset(f,0x3f,sizeof(f));
memset(g,0xcf,sizeof(g));
for(i=1,n=gi();i<=n;++i) a[i]=a[i+n]=gi();
for(i=1;i<=n<<1;++i)
f[i][i]=g[i][i]=0,pf[i][i]=pg[i][i]=i,s[i]=s[i-1]+a[i];
for(i=n<<1;i>=1;--i)
for(j=i+1;j<=n<<1&&j-i+1<=n;++j) {
for(k=pf[i][j-1];k<=pf[i+1][j];++k)
if(f[i][k]+f[k+1][j]+s[j]-s[i-1]<f[i][j])
f[i][j]=f[i][k]+f[k+1][j]+s[j]-s[i-1],pf[i][j]=k;
g[i][j]=max(g[i][j-1],g[i+1][j])+s[j]-s[i-1];
//最大值没有决策单调性，但是为什么可以是上面那样？
}
ans1=0x3f3f3f3f,ans2=0;
for(i=1;i<=n;++i)
ans1=min(ans1,f[i][i+n-1]),ans2=max(ans2,g[i][i+n-1]);
printf("%d\n%d\n",ans1,ans2);
return 0;
}
c.[√] 邮局
sol:
此题不难想到设\(f[i,j]\)表示前面j个村庄建了i个邮局的最小距离和。
转移为：
\[
f[i,j]=min_{0≤k<j}\{f[i-1,k]+cost(k+1,j)\}
\]
关于cost的计算显然取中间值最优。
还是打表发现，f具有决策单调性。
那么注意到此处i正序枚举,j可正可倒，但为了套上面讲到的模型，让j倒序枚举，然后就有：
\(p[i-1,j]≤p[i,j]≤p[i,j+1]\ (p[x,y]代表状态(x,y)的最优决策)\)
但是由于每次枚举到下一个i时，\(p[i,\_]\)全为0,所以需要先把\(p[i,m+1]=m\)，然后再转移。
#include<cmath>
#include<string>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define RG register
#define IL inline
#define LL long long
#define DB double
using namespace std;
IL int gi() {
RG int x=0,w=0; char ch=getchar();
while (ch<'0'||ch>'9') {if (ch=='-') w=1;ch=getchar();}
while (ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
return w?-x:x;
}
const int N=303;
const int M=3003;
int n,m,a[M],f[N][M],p[N][M],pre[M][M],suf[M][M];
IL int dist(int l,int r,int mid) {return pre[mid][r]+suf[mid][l];}
IL int calc(int l,int r) {
if((r-l+1)&1) return dist(l,r,l+r>>1);
else return min(dist(l,r,l+r-1>>1),dist(l,r,l+r+1>>1));
}
int main()
{
RG int i,j,k,tmp;
m=gi(),n=gi();
for(i=1;i<=m;++i) a[i]=gi();
sort(a+1,a+m+1);
for(i=1;i<=m;++i)
for(j=i+1;j<=m;++j)
pre[i][j]=pre[i][j-1]+a[j]-a[i];
for(i=m;i>=1;--i)
for(j=i-1;j>=1;--j)
suf[i][j]=suf[i][j+1]+a[i]-a[j];
memset(f,0x3f,sizeof(f));
f[0][0]=0;
for(i=1;i<=n;++i) {
p[i][m+1]=m;
for(j=m;j>=1;--j)
for(k=p[i-1][j];k<=p[i][j+1];++k) {
tmp=f[i-1][k]+calc(k+1,j);
if(tmp<f[i][j]) f[i][j]=tmp,p[i][j]=k;
}
}
printf("%d\n",f[n][m]);
return 0;
}