区间dp总结
1) 什么情况要枚举断点合并两个区间\(f[l][k]+f[k+1][r]\)？
- 为了考虑区间与区间合并导致的新贡献的加入,因为一步一步转移会漏掉细节，具体来说就是区间的答案合并后会改变，变少或变多(P4170)。
2) 什么时候可以不用/不能枚举断点？
- 当区间不具备可合并性(P5044/CF360B)或题目明确转移是一步一步的(P1005)或枚不枚举断点无所谓，但一步一步转移可以减少状态数的(P4767)
3) 像P4158和P4767这种带有数量限制的序列问题就不算区间dp了，算线性dp.
~~总之具体情况靠直觉~~
统计最值类
P1880
模板题
注意环形需要开2倍空间
P1063
与P1880十分类似，注意每次增加的数值为\(a[b]* a[k+1]* a[e+1]\)
转移方程：
for(int l=1;l<=n+n;++l){
for(int b=1;b+l-1<=n+n;++b){
int e=b+l-1;
for(int k=b;k<e;++k){
dp[b][e]=max(dp[b][e],dp[b][k]+dp[k+1][e]+a[b]*a[k+1]*a[(e+1)]);
}
}
}
P1220
注意到特殊性质：
最佳方案一定取得是连续的区间。
假如有:
5 3
2 10
3 20
5 20
6 30
8 10
for(int l=c;l>=1;--l){
for(int r=c;r<=n;++r){
dp[l][r][l]=min(dp[l][r][l],min(dp[l+1][r][l+1]+(a[l+1]-a[l])*(sum-x[r]+x[l]),dp[l+1][r][r]+(a[r]-a[l])*(sum-x[r]+x[l])));
dp[l][r][r]=min(dp[l][r][r],min(dp[l][r-1][l]+(a[r]-a[l])*(sum-x[r-1]+x[l-1]),dp[l][r-1][r-1]+(a[r]-a[r-1])*(sum-x[r-1]+x[l-1])));
}
}
P2466
与上面的相似，每次移动后小球都会下落，相当于消耗了最终的价值，所以最小化这个消耗即可，转移方程同上面。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define int long long
using namespace std;
typedef double db;
const int N=1e3+10;
const db INF=1e16;
db f[N][N][2],res,ans;
struct node{
int x,y,v;
}a[N];
int s[N],sum,n,x;
bool cmp(node a,node b);
void init();
void dp();
int Abs(int x);
db Min(db a,db b);
signed main(){
scanf("%lld%lld",&n,&x);
for(int i=1;i<=n;++i) scanf("%lld",&a[i].x);
for(int i=1;i<=n;++i) scanf("%lld",&a[i].y);
for(int i=1;i<=n;++i) scanf("%lld",&a[i].v);
init();
dp();
return 0;
}
bool cmp(node a,node b){
return a.x<b.x;
}
int Abs(int x){
return x>=0?x:-x;
}
db Min(db a,db b){
return a<=b?a:b;
}
void init(){
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;++i) s[i]=s[i-1]+a[i].v,sum+=a[i].v;
for(int i=1;i<=n;++i) res+=(db)(a[i].y)/1000.0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) f[i][j][0]=f[i][j][1]=INF;
for(int i=1;i<=n;++i) f[i][i][0]=f[i][i][1]=(db)(Abs(x-a[i].x)*sum)/1000.0;
}
void dp(){
for(int l=2;l<=n;++l){
for(int b=1;b+l-1<=n;++b){
int e=b+l-1;
f[b][e][0]=Min(f[b][e][0],Min(f[b+1][e][0]+(db)(Abs(a[b+1].x-a[b].x)*(sum-s[e]+s[b]))/1000.0,f[b+1][e][1]+(db)(Abs(a[e].x-a[b].x)*(sum-s[e]+s[b]))/1000.0));
f[b][e][1]=Min(f[b][e][1],Min(f[b][e-1][0]+(db)(Abs(a[e].x-a[b].x)*(sum-s[e-1]+s[b-1]))/1000.0,f[b][e-1][1]+(db)(Abs(a[e].x-a[e-1].x)*(sum-s[e-1]+s[b-1]))/1000.0));
}
}
ans=Min(f[1][n][0],f[1][n][1]);
printf("%.3lf",res-ans);
}
/*
3 3
-4 -2 2
22 30 26
1 9 8
*/
P1650
这道题一个重要的性质就是：对于田忌全不输的出马序列，一定满足从大到小:
$$A_1 \geq A_2 \geq... \geq A_n\
假设有A_i<A_{i+1},且A_i\geq B_i,A_{i+1}\geq B_{i+1},B_i\geq B_{i+1},\那么就可以交换A_i 和A_{i+1}。 $$ 同样能证明对于田忌全输的序列满足从小到大。
于是，任意的状态都是从A序列头和为去除一些元素后形成的连续序列。这样的话，区间DP和贪心都可以做了。
设f[i][j]表示A序列还剩i到j匹马时的最优解。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2010;
int n;
int a[N],b[N],f[N][N];
bool cmp(int a,int b){
return a>b;
}
int main(){
memset(f,-0x3f,sizeof f);
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
f[1][n]=0;
for(int num=0,l=n-1;l>=1;--l){
num=n-l;
for(int i=1,j=0;i+l-1<=n;++i){
j=i+l-1;
int g1=a[i-1]>b[num]?200:(a[i-1]==b[num]?0:-200);
int g2=a[j+1]>b[num]?200:(a[j+1]==b[num]?0:-200);
f[i][j]=max(f[i][j],f[i-1][j]+g1);
f[i][j]=max(f[i][j],f[i][j+1]+g2);
}
}
int ans=-0x3f3f3f3f;
for(int i=1,tmp=0;i<=n;++i){
tmp=f[i][i]+(a[i]>b[n]?200:(a[i]==b[n]?0:-200));
ans=max(ans,tmp);
}
printf("%d",ans);
return 0;
}
/*
3
92 83 71
95 87 74
4
87 84 83 82
90 87 86 85
4
87 85 84 83
90 87 86 82
*/
P2587 ~~承接上文~~
这道题数据范围就没那么友好了，费用流和dp都行不通，此时我们考虑贪心。
因为有了连续性，所以我们只需要比较a，b序列的头和尾就行了，所以有四个指针。
下面分情况讨论取最大值：
0.先从大到小排序
1.a[la]>b[lb],因为赢的序列都是单调递减的，所以不用犹豫直接怼，赢下一局；
2.a[la]<b[lb],此时b[lb]就是所有数中最大的，a不管出什么都一定输，所以破罐破摔，贪心的取a的最小值怼它。
3.a[la]==b[lb].
因为a[la]已经与b[lb]相等，那么a[la]一定大于等于b[lb+1],此时如果a最小怼b最大输，a最大怼b次大赢，获得的结果一定不差于a最大与b最大怼成平局（因为消耗了b两员大将，而一胜一负与一平局结果一样）,所以遇到平局就再分类：
1) a[ra]>b[rb],既然能赢，那就怼
2) a[ra]<=b[rb],此时a[ra]时最小的，一定会输，与其让它与b小的输，不如让他消耗掉b最大的。注意当序列只有一个数时，a[ra]==b[lb]要特判。
那么最小值同理。
code time:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int a[N],b[N],n;
bool cmp(int a,int b){
return a>b;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
for(int i=1;i<=n;++i)scanf("%d",&b[i]);
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
int la=1,lb=1,ra=n,rb=n,ans=0;
for(int i=1;i<=n;++i){
if(a[la]>b[lb]){
ans+=2;
la++;
lb++;
}else if(a[la]<b[lb]){//b[lb] biggest
ra--;
lb++;
}else{
if(a[ra]>b[rb]){
ans+=2;
ra--;
rb--;
}else{//a[ra] smallest
if(a[ra]==b[lb])ans+=1;
ra--;
lb++;
}
}
}
printf("%d ",ans);
la=1,lb=1,ra=n,rb=n,ans=0;
for(int i=1;i<=n;++i){
if(a[ra]<b[rb]){
ra--;
rb--;
}else if(a[ra]>b[rb]){//b[rb] smallest
ans+=2;
la++;
rb--;
}else{
if(a[la]<b[lb]){
la++;
lb++;
}else{//a[la] biggest
ans+=2;
if(a[la]==b[rb])ans-=1;
la++;
rb--;
}
}
}
printf("%d",ans);
return 0;
}
P3205
注意到每种队形只有两种状态，一种是左边的最后进队，一种时右边的最后进队，因此定义状态：
f[i][j][0/1]表示i到j区间的左/右最后进队的队形
则转移方程：
memset(dp,0,sizeof dp);
for(int i=1;i<=n;++i)dp[i][i][0]=1,dp[i][i][1]=0;//注意，是坑
for(int l=1;l<=n;++l){
for(int b=1;b+l-1<=n;++b){
int e=b+l-1;
if(a[b]<a[b+1])dp[b][e][0]=(dp[b][e][0]+dp[b+1][e][0])%P;
if(a[b]<a[e])dp[b][e][0]=(dp[b][e][0]+dp[b+1][e][1])%P;
if(a[e]>a[b])dp[b][e][1]=(dp[b][e][1]+dp[b][e-1][0])%P;
if(a[e]>a[e-1])dp[b][e][1]=(dp[b][e][1]+dp[b][e-1][1])%P;//%P
}
}
P1005
与3205很像，~~就是高精度太烦人了~~
设f[i][j]表示i到j都取完的最大值.转移方程：
for(int i=1;i<=m;++i){
f[i][i]=tmp[i]<<1;
}
for(int l=2;l<=m;++l){
for(int b=1;b+l-1<=m;++b){
int e=b+l-1;
f[b][e]=max(f[b][e],2*f[b][e-1]+2*tmp[e]);
f[b][e]=max(f[b][e],2*f[b+1][e]+2*tmp[b]);
}
}
P3147
巧妙地将大的二维状态变为小的
设f[k][i]表示从左端点i位置能合成k的右端点位置信息
则转移方程：
f[k][i]=f[k-1][f[k-1][i]]
复杂度\(\Theta(NK)\)
for(int i=1;i<=n;++i){
f[a[i]][i]=i+1;
maxn=max(maxn,a[i]);
}
for(int k=1;k<=58;++k){
for(int i=1;i<=n;++i){
f[k][i]=f[k-1][f[k-1][i]]==0?f[k][i]:f[k-1][f[k-1][i]];
if(f[k][i])maxn=max(k,maxn);
}
}
P4170
若a[b]==a[e],则在一开始可以都染了，所以继承f[b+1][e]和f[b][e-1]
若a[b]!=a[e],那就普通地断成两段。
for(int l=1;l<=n;++l){
for(int b=1;b+l-1<=n;++b){
int e=b+l-1;
if(a[b]==a[e])f[b][e]=min(f[b][e],f[b+1][e]);
if(a[b]==a[e])f[b][e]=min(f[b][e],f[b][e-1]);
for(int k=b;k<e;++k){
f[b][e]=min(f[b][e],f[b][k]+f[k+1][e]);
}
}
}
因为枚举断点可以把大区间中的小区间枚举出来，从而不会漏掉细节。
以P4170举例，面对ABCBAABA这个串时，如果一步一步枚举，就不能看到BCB可以两步解决，而是会判定为3步:
AABA 2
BAABA 3
CBAABA 4
BCBAABA 5 (X)
这是因为 CB 这个串中的B被包在了大区间里面，所以没有枚举到。
P1622
设f[i][j]表示第i号到第j号犯人全部释放的最小值，并且包含a[i-1]到a[j+1]之间的所有房间。
例：0---3---6---14---21
则f[1][2]表示---3---6---
注意a的两端应该设为0和n+1，不然整个区间就短了2个单位
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+10,M=110;
int f[N][N];
int a[N];
int n,m;
bool cmp(int a,int b){
return a<b;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)scanf("%d",&a[i]);
sort(a+1,a+m+1,cmp);
a[0]=0;
a[m+1]=n+1;
for(int l=1;l<=m;++l){
for(int b=1;b+l-1<=m;++b){
int e=b+l-1;
f[b][e]=999999999;
for(int k=b;k<=e;++k){
f[b][e]=min(f[b][e],f[b][k-1]+f[k+1][e]+a[e+1]-a[b-1]-1-1);
}
}
}
printf("%d",f[1][m]);
return 0;
}
P7914
~~\(O(n^3)\)能过是我没想到的~~
这道题最麻烦的地方是判重。
假设有一个AB串是这样的：
()()()
那么，合并区间时肯定要枚举断点，而如果不加限制的话，会出现这种情况：
1.()+()()
2.()()+()
同样的，ASB串也会出现这种情况。
因此，我们可以采用类似线性筛的思想取判重。
线性筛是让每个数都由最小的质数筛掉，如12只由2 6筛，而不能由3 4筛掉。
同理，()()()只能由()+()()更新，而不能由()()+()更新。
那么我们就可以这样设状态：
struct node{
int A,S,AS,SA,AA,AAS,SAA;
}f[N][N];
"最小"是指严格由括号包着，如(),(S),(A),(AS),(SA)都属于最小,即A;
而AB,ASB属于非最小,即AA。
换句话说，就是不可再拆分的A串。
那么转移方程就好推了。
1) *和()直接初始化得到。
2) S可以由更小的S推出来，只要长度小于等于k并且不覆盖固定括号就行。
3) A可以由所有(),(S),(AS),(SA),(A),(AAS),(SAA)得来。
4) SA,AS,AAS,SAA可以枚举断点：AS=A S,SAA=S AA等。
5) AA同样枚举断点，可以由最小得A和AS与A和AA拼接得来：AA=(A+AS)* (A+AA);
code time:
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=550,P=1e9+7;
struct node{
int A,S,AS,SA,AA,AAS,SAA;
}f[N][N];
int n,k,a[N];
char ch[N];
bool ok(int i,int j){//(...)
if(a[i]!=1 && a[i]!=-2 && a[j]!=1 && a[j]!=-1)return true;
else return false;
}
bool getS(int l,int i,int j){
if(l>k)return false;
if((f[i][j-1].S==1 && a[j]!=-1 && a[j]!=-2) || (f[i+1][j].S==1 && a[i]!=-1 && a[i]!=-2))return true;
else return false;
}
void init(){
memset(f,0,sizeof f);
for(int i=1;i<=n;++i){
if(a[i]==0 || a[i]==1){
f[i][i].S=1;//*
}else f[i][i].S=0;
}
for(int i=1;i+1<=n;++i){
if(ok(i,i+1)){
f[i][i+1].A=1;//()
}else f[i][i+1].A=0;
}
}
void dp(){
init();
for(int l=1;l<=n;++l){
for(int i=1,j=0;i+l-1<=n;++i){
j=i+l-1;
if(ok(i,j)){
f[i][j].A=(f[i][j].A+f[i+1][j-1].AA+f[i+1][j-1].A+f[i+1][j-1].S+f[i+1][j-1].SA+f[i+1][j-1].AS+f[i+1][j-1].SAA+f[i+1][j-1].AAS)%P;
//(AA) (S) (A) (AS) (SA) (AAS) (SSA)
}
for(int p=i;p<j;++p){
f[i][j].AS=(f[i][j].AS+f[i][p].A*f[p+1][j].S)%P;
//AS
f[i][j].SA=(f[i][j].SA+f[i][p].S*f[p+1][j].A)%P;
//SA
f[i][j].AAS=(f[i][j].AAS+f[i][p].AA*f[p+1][j].S)%P;
//AAS
f[i][j].SAA=(f[i][j].SAA+f[i][p].S*f[p+1][j].AA)%P;
//SAA
}
for(int p=i;p<j;++p){
f[i][j].AA=(f[i][j].AA+(f[i][p].A+f[i][p].AS)*(f[p+1][j].A+f[p+1][j].AA))%P;
//AB
//ASB
}
if(getS(l,i,j)) f[i][j].S=1;//S
}
}
printf("%lld",(f[1][n].A+f[1][n].AA)%P);
}
signed main(){
//freopen("bracket4.in","r",stdin);
scanf("%lld%lld",&n,&k);
scanf("%s",ch);
for(int i=0;i<n;++i){
if(ch[i]=='*'){
a[i+1]=1;
}else if(ch[i]=='('){
a[i+1]=-1;
}else if(ch[i]==')'){
a[i+1]=-2;
}else{//?
a[i+1]=0;
}
}
dp();
return 0;
}
/*
4 2
()()
6 2
()()()
7 3
(*??*??
(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)
10 2
???(*??(?)
(**(*))(*)
(()(*))(*)
()((*))(*)
()*(**)(*)
(*)(**)(*)
()*(*)*(*)V
(*)(*)*(*)
()*(*()()) //()
(*)(*()())
(*)(*)(()) //)(
()*(*)(())
(()(**)()) //*)
()((**)())
(**(**)())
(**(*)*())V //)*
()((*)*())
(()(*)*())
(*((*))()) //))
((*(*))())
*/
当枚举的区间长度为l时，l是从1到n变化的，这使得每次再枚举区间左端点的次数时从n到1变化的，而每次枚举断点都要枚举l次，所以总的时间复杂度就是 $$\sum_{i=1}^n(n-i+1)* i=\sum_{i=1}^nf(i)\ 即对f(i)积分：\ \int_1^nf(i)di=F(n)-F(1) \ \because f(i)= -i^2+(n+1)i \
\therefore F(i)=-\frac13i^3+\frac{n+1}{2}i^2\
\therefore 原式=-\frac13n^3+\frac12n^3+\frac12n^2+\frac13-\frac12-\frac n2\ =\frac16n^3+\frac12n^2-\frac12n-\frac16\ =O(\frac16 n^3) $$
~~这使得我们可以不用四边形优化直接水过~~
P2470
好题。
为了方便表示，假设每个串的开头都有\(M\)，最后答案\(-1\)即可。
我们发现，能够压缩的串只有一种，就是中间没有\(M\)的，前后相同的串。
例如,\(abcbcabcbc\)前后相等，可以压缩成\(abcbcR\).
虽然\(aMbcR\)是\(abcbc\)的一个压缩，但因为\(aMbcRaMbcR\)中间含有\(M\)且\(M\)前有东西\((a)\)，所以不能变成\(aMbcRR(abcbcbcbc)\)。
由此可以设两种状态，\(f[i][j][0]\)和\(f[i][j][1]\).
\(f[i][j][0]\)表示只有开头有一个\(M\)，并且中间不包含\(M\)的状态。
\(f[i][j][1]\)表示开头有\(M\),并且中间有一个及以上\(M\)的状态。
那么对于长度为偶数且前后相等的串，可以加一个\(R\)压缩。
对于只有一个\(M\)的状态，可以由小的区间加上未压缩的原串的来。
对于多个\(M\)的状态则可以枚举断点。
code time:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=55;
int f[N][N][2];
int n;
int a[N];
char ch[N];
bool check(int l,int r){
int len=r-l+1;
if(len&1)return 0;
int mid=l+r>>1;
for(int i=l;i<=mid;++i)
if(a[i]!=a[i-l+mid+1])return 0;
return 1;
}
void init(){
scanf("%s",ch);
n=strlen(ch);
for(int i=0;i<n;++i)a[i+1]=ch[i]-'a'+1;
for(int i=1;i<=n;++i)
for(int j=i;j<=n;++j)f[i][j][0]=f[i][j][1]=j-i+1+1;
}
void dp(){
for(int l=1;l<=n;++l){
for(int i=1,j,mid;i+l-1<=n;++i){
j=i+l-1;
mid=i+j>>1;
if(check(i,j))f[i][j][0]=min(f[i][j][0],f[i][mid][0]+1);
for(int k=i;k<j;++k){
f[i][j][0]=min(f[i][j][0],f[i][k][0]+j-k);
f[i][j][1]=min(f[i][j][1],min(f[i][k][0],f[i][k][1])+min(f[k+1][j][0],f[k+1][j][1]));
}
}
}
}
int main(){
init();
dp();
printf("%d",min(f[1][n][0],f[1][n][1])-1);
return 0;
}
记忆化搜索
UVA10559
看到这题很容易想到\(f[i][j]\)表示将\(i\)到\(j\)全部消除能产生的最大贡献。
然而，问题在于，不一定将这个区间所有都消除的决策就是最优决策，他不满足最优子结构，即最优解不一定有子问题最优解得来。
比如：可以将区间中间掏空，留下某些颜色的方块与区间外的同色块一起消除。
这是说明，状态描述不够清晰。我们要加维。
设\(f[i][j][k]\)表示消除区间\(i\)到\(j\)以及与\(a[j]\)同色的，右边的\(k\)个块产生的最大贡献。
此时对于\(j\)和它右边的\(k\)个同色块有消除和保留两种决策。
1) 消除
这时只要将\(a[j]\)与右边\(k\)个块一起消除就行。贡献\((k+1)^2\)。剩下的另作考虑。 $$ f[i][j][k]=max(f[i][j][k],dfs(i,j-1,0)+(k+1)* (k+1)); $$
至于将连续\(x\)个\(j\)左边的同色块也一同消除这个决策，会被包含在保留中。
2) 保留
保留指保留着\(j\)和它右边的\(k\)个同色块，与区间左边的一些块一起消去，即累积\(k+1+p\)个同色块一起消去。
当然，不一定要将所有同色块都一次性消去，可能右边一部分连续消除，左边的所有同色块都单独消除，让他们中间的其他颜色块连续消除才是最佳答案。
所以要枚举断点，而这个断点与\(a[j]\)同色。这个可以预处理出\(pre[j]\).
$$ f[i][j][k]=max(f[i][j][k],dfs(i,p,k+1)+dfs(p+1,j-1,0)); $$
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=220;
int f[N][N][N];
int pre[N],vis[N],a[N];
int T,n;
void init() {
memset(pre,0,sizeof pre);
memset(vis,0,sizeof vis);
memset(f,0,sizeof f);
scanf("%lld",&n);
for(int i=1; i<=n; ++i) {
scanf("%lld",&a[i]);
if(vis[a[i]])pre[i]=vis[a[i]];
vis[a[i]]=i;
}
}
int dfs(int i,int j,int k) {
if(i>j)return 0;
if(f[i][j][k])return f[i][j][k];
f[i][j][k]=max(f[i][j][k],dfs(i,j-1,0)+(k+1)*(k+1));
for(int p=pre[j]; p>=i; p=pre[p]) {
f[i][j][k]=max(f[i][j][k],dfs(i,p,k+1)+dfs(p+1,j-1,0));
}
return f[i][j][k];
}
signed main() {
scanf("%lld",&T);
for(int t=1; t<=T; ++t) {
init();
printf("Case %lld: %lld\n",t,dfs(1,n,0));
}
return 0;
}
P5044 naive版
如果考虑\(19pts\)可以区间dp,\(O(n^2)\).
设\(f[i][j]\)表示从\(i\)到\(j\)的最小代价。
首先设\(x\)为区间最大值的位置。
我们考虑当选取的点在\(x\)左边时，右边的点贡献全部为\(a_x\),左边的点贡献则为\(f[i][x-1]\),右边同理，所以转移方程：
-
结论：
-
该题具有单调性，即每个点的贡献只由区间最大值及其位置决定，这样转移时就可以只考虑最大值，降低转移难度。
-
找单调性时就要考虑哪些条件会使贡献单一化，比如最大值会使它左/右的区间贡献全部变为自己。
P4767 naive版
设\(f[i][j]\)表示前\(i\)个村庄放了\(j\)个邮局。
一个一个转移，方程为
其中\(w(k+1,i)\)为计算\(k+1\)到\(i\)的最小距离和。
因为数学上距离和一定是中位数最小，所以直接暴力求解即可。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e3+10;
int f[N][N];
int p,v;
int a[N];
int w(int l,int r){
int mid=l+r>>1,ans=0;
for(int i=l;i<=mid-1;++i)ans+=a[mid]-a[i];
for(int i=mid+1;i<=r;++i)ans+=a[i]-a[mid];
return ans;
}
int main(){
scanf("%d%d",&v,&p);
for(int i=1;i<=v;++i)scanf("%d",&a[i]);
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=v;++i){
for(int j=1;j<=p;++j){
for(int k=0;k<i;++k){
f[i][j]=min(f[i][j],f[k][j-1]+w(k+1,i));
}
}
}
printf("%d",f[v][p]);
return 0;
}
-
结论：
-
\(w\)的求解具有单调性，可以帮助简化转移。
-
如果枚举断点合并两个区间的话，既要将邮局个数\(p\)合并，又要将左右端点\(l,r\)合并，要两个断点，肯定不行。事实上，枚举断点合并区间只有在合并两个区间时，两个区间之间会有新贡献时，才需要。像这题，左右区间合并就是合并了，之间没有新贡献，邮局个数的增加也没有新贡献，就可以一个一个地，不用右区间值地转移。
-
考虑\([1\ 2\ 5]\ [6\ 7\ 8]\),这样的数据会出错？不，因为\([1\ 2]\ [5\ 6\ 7\ 8]\)即可求出正确答案。
P4676
对于每个区间，我们设\(f[i][j]\)表示将完全属于这个区间的所有外星人全部消除的最小值。
那么我们先\(O(n)\)找出这个区间内距离最大的外星人\(p\)。因为它最大，不会被别人顺带消除，所以必有一个操作是针对这个最大外星人，所以只需要枚举\([a[p].l,a[p].r]\)这个区间的断点即可，那么东线自然是\(a[p].d\),转移方程:
为什么要完全属于？因为如果跨越当前区间到别的地方，那么这个最大就可能被多个断点枚举到，相当于算重了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int N=660,INF=1e18;
struct node{
int l,r,d;
}a[N];
int f[N][N];
int b[N];
int T,n,cnt,tot;
bool cmp(int a,int b){return a<b;}
void lsh(){
sort(b+1,b+cnt+1,cmp);
tot=unique(b+1,b+cnt+1)-b-1;
for(int i=1;i<=n;++i) a[i].l=lower_bound(b+1,b+tot+1,a[i].l)-b,a[i].r=lower_bound(b+1,b+tot+1,a[i].r)-b;
}
void dp(){
for(int i=1;i<=tot;++i)
for(int j=i;j<=tot;++j) f[i][j]=INF;
for(int l=1;l<=tot;++l){
for(int i=1;i+l-1<=tot;++i){
int j=i+l-1,pos=-1,maxn=-1;
for(int k=1;k<=n;++k) if(i<=a[k].l && a[k].r<=j && a[k].d>maxn) maxn=a[k].d,pos=k;
if(pos==-1){f[i][j]=0;continue;}
for(int k=a[pos].l;k<=a[pos].r;++k) f[i][j]=min(f[i][j],f[i][k-1]+f[k+1][j]+a[pos].d);
}
}
printf("%lld\n",f[1][tot]);
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%lld",&n);cnt=0;tot=0;
for(int i=1;i<=n;++i) scanf("%lld%lld%lld",&a[i].l,&a[i].r,&a[i].d),b[++cnt]=a[i].l,b[++cnt]=a[i].r;
lsh();
dp();
}
return 0;
}
P5851
与上面类似，只是每次\(dp\)是再枚举区间就会变成\(O(n^2m)=O(n^4)\)的复杂度，所以我们预处理一下\(g[k][i][j]\),表示对于\([i,j]\)这个区间中包含\(k\)点的，所有子区间的最大值。
#include<iostream>
#include<cstdio>
#include<cstring>
#define int long long
using namespace std;
const int N=330;
int a[N][N][N];
int f[N][N];
int n,m,l,r,w;
void init(){
for(int k=1;k<=n;++k)
for(int i=k;i>=1;--i)
for(int j=k;j<=n;++j)
a[k][i][j+1]=max(a[k][i][j+1],a[k][i][j]),a[k][i-1][j]=max(a[k][i-1][j],a[k][i][j]);
}
void dp(){
for(int l=1;l<=n;++l)
for(int i=1;i+l-1<=n;++i){
int j=i+l-1;
//for(int k=i;k<j;++k) f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
for(int k=i;k<=j;++k) f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+a[k][i][j]);
}
printf("%lld",f[1][n]);
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=m;++i){
scanf("%lld%lld%lld",&w,&l,&r);
for(int k=l;k<=r;++k) a[k][l][r]=max(a[k][l][r],w);
}
init();
dp();
return 0;
}