这类问题大概长这样:
求一个排列 \(p_{1\sim n}\),最小(大)化如下值:
\[\sum\limits_{i=1}^{n-1}f(p_i,p_{i+1})\\ f(i,j)= \left\{ \begin{array}{**lr**} g(i)+h(j),i<j\\ h(i)+g(j),i>j \end{array} \right. \]那么就可以用如下方法 \(O(n^2)\) 解决:
-
从小到大向序列中插入元素;
-
记 \(f_{i,j,0/1,0/1}\) 表示,前 \(i\) 个数插入后,分成了 \(j\) 段,首尾分别是否确定 的最小(大)值。
这里的分段表示后面大的数不能插在一段中间
-
对 \(i\) 插入位置分类讨论:
- 插入首位:
- 在首位新开一个段;
- 在第一个段最前面插入。
- 插入末位:
- 在末位新开一个段;
- 在最后一个段后面插入。
- 插入中间:
- 在任意位置(可以在开头或末位)插入一段
需要讨论首位末位是否确定判断是否可以插入开头和末位
- 插入【不是第一个段的段】的开头;
- 插入【不是最后一个段的段】的末尾;
- 插入两个段的中间并合并两个段。
- 在任意位置(可以在开头或末位)插入一段
- 插入首位:
-
然后就做完了,改成计数也是没问题的。
例题
CF704B Ant Man
板题,直接上即可。
甚至帮你决定了要不要插入首位和末位。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=5e3+10;
const ll INF=1e18;
int n,st,ed,x[N],a[N],b[N],c[N],d[N];
ll f[N][N];
void chkmin(ll &x,ll y){
if(x>y)x=y;
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d%d",&n,&st,&ed);
for(int i=1;i<=n;i++)scanf("%d",&x[i]);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=n;i++)scanf("%d",&c[i]);
for(int i=1;i<=n;i++)scanf("%d",&d[i]);
memset(f,0x3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j>(i>st)+(i>ed))chkmin(f[i][j],f[i-1][j-1]+b[i]-x[i]+d[i]-x[i]);
if(j>(i>st)&&i!=ed)chkmin(f[i][j],f[i-1][j]+c[i]+b[i]);
if(j>(i>ed)&&i!=st)chkmin(f[i][j],f[i-1][j]+a[i]+d[i]);
if(i!=st&&i!=ed)chkmin(f[i][j],f[i-1][j+1]+x[i]+c[i]+x[i]+a[i]);
}
}
cout<<f[n][1]-(b[st]-x[st])-(d[ed]-x[ed]);
return 0;
}
P2612 [ZJOI2012] 波浪
概率->计数,需要数据分治。
\(K\le 8\) 时可用 long double,否则用 __float128。
由于这题的特殊性,\(g(i)=h(i)\),所以不需要记录首尾分别是否确定。
只要记录首尾确定了几个即可。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int n,m,k;
namespace Solve1{
const int N=1e2+10,M=N*N,zero=M/2;
long double f[2][3][N][M];
void solve(){
f[0][0][0][zero]=1;
for(int i=1,now=1,las=0;i<=n;i++,swap(now,las)){
memset(f[now],0,sizeof f[now]);
for(int x=0;x<3;x++){
for(int j=0;j<=n;j++){
for(int k=0;k<M;k++){
if(f[las][x][j][k]==0)continue;
if(j>1&&k+i*2<M)f[now][x][j-1][k+i*2]+=f[las][x][j][k]*(j-1)/i;
if(k-i*2>=0)f[now][x][j+1][k-i*2]+=f[las][x][j][k]*(j+1-x)/i;
if(j)f[now][x][j][k]+=f[las][x][j][k]*(j*2-x)/i;
if(x<2){
if(j&&k+i<M)f[now][x+1][j][k+i]+=f[las][x][j][k]*(2-x)/i;
if(k-i>=0)f[now][x+1][j+1][k-i]+=f[las][x][j][k]*(2-x)/i;
}
}
}
}
}
long double ans=0;
for(int i=m;zero+i<M;i++)ans+=f[n&1][2][1][zero+i];
printf("%.*Lf",k,ans);
}
}
namespace Solve2{
const int N=50+10,M=N*N,zero=M/2;
__float128 f[2][3][N][M];
void solve(){
f[0][0][0][zero]=1;
for(int i=1,now=1,las=0;i<=n;i++,swap(now,las)){
memset(f[now],0,sizeof f[now]);
for(int x=0;x<3;x++){
for(int j=0;j<=n;j++){
for(int k=0;k<M;k++){
if(f[las][x][j][k]==0)continue;
if(j>1&&k+i*2<M)f[now][x][j-1][k+i*2]+=f[las][x][j][k]*(j-1)/i;
if(k-i*2>=0)f[now][x][j+1][k-i*2]+=f[las][x][j][k]*(j+1-x)/i;
if(j)f[now][x][j][k]+=f[las][x][j][k]*(j*2-x)/i;
if(x<2){
if(j&&k+i<M)f[now][x+1][j][k+i]+=f[las][x][j][k]*(2-x)/i;
if(k-i>=0)f[now][x+1][j+1][k-i]+=f[las][x][j][k]*(2-x)/i;
}
}
}
}
}
__float128 ans=0;
for(int i=m;zero+i<M;i++)ans+=f[n&1][2][1][zero+i];
int d=(int)ans;
printf("%d.",d);
ans-=d;
for(int d;k--;){
d=ans*10+(k?0:0.5);
printf("%d",d);
ans=ans*10-d;
}
}
}
int main(){
freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m>>k;
if(k<=8)Solve1::solve();
else Solve2::solve();
return 0;
}
标签:插入,--,ll,long,zhengjun,int,now,dp,las
From: https://www.cnblogs.com/A-zjzj/p/17573343.html