【BZOJ2817】[ZJOI2012]波浪(动态规划)

题面

BZOJ

洛谷

题解

首先这个差值最大也就是\(n^2\)级别的。

那么这样子就可以压进状态啦。

我们把这个操作看成一个个加数的操作,按照从小往大的顺序依次把每个数放到一个合法的格子上面去,那么对于先放的数,对于答案的贡献就是负的,否则就是正的。

那么每次放入一个数,考虑其贡献是什么。

如果其左右都没有数,则贡献是\(-2x\)。

如果一侧有数,则贡献是\(0\)。

如果两侧都有数,则贡献是\(2x\)。

显然填好的数是一段段的,那么上述的操作可以理解为联通块的合并操作。

第一个是新建一个联通块,第二个是扩展一个联通块,第三个是合并两个联通块。

那么我们的状态就可以写成,当前填第\(i\)个数,贡献之和是\(j\),一共有\(k\)个联通块。

这样是对的吗?

并不是,还有一点小问题,即填在边界上的数并没有那么好处理。

所以再加上一维表示边界上填数的数的个数(有两个边界啊QwQ)

那么转移的时候大力讨论一下就好啦~。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int py=4500;
int n,M,K;
namespace Task1
{
void Output(long double ans)
{
printf("0.");
for(int i=1;i<=K;++i)
{
ans*=10;int x=(i==K)?(ans+0.5):ans;
printf("%d",x);ans-=x;
}
puts("");
}
int main()
{
static long double f[2][105][9005][3],ans;
f[0][0][py][0]=1;
for(int i=1,nw=1,pw=0;i<=n;++i,nw^=1,pw^=1)
{
memset(f[nw],0,sizeof(f[nw]));
for(int j=0;j<i;++j)
for(int k=0;k<=4500+py;++k)
for(int l=0;l<=2;++l)
if(f[pw][j][k][l])
{
if(k-i-i>=0)f[nw][j+1][k-i-i][l]+=f[pw][j][k][l]*(j+1-l);//一个新的连通块
if(j)f[nw][j][k][l]+=f[pw][j][k][l]*(j+j-l);//作为一个连通块的一端
if(j>=2&&k+i+i<=9000)f[nw][j-1][k+i+i][l]+=f[pw][j][k][l]*(j-1);//连接两个连通块
if(k-i>=0)f[nw][j+1][k-i][l+1]+=f[pw][j][k][l]*(2-l);//作为一个端点
if(j&&k+i<=9000)f[nw][j][k+i][l+1]+=f[pw][j][k][l]*(2-l);//一个连通块延伸到了边界
}
}
for(int i=M;i<=4500;++i)ans+=f[n&1][1][py+i][2];
for(int i=1;i<=n;++i)ans/=i;
Output(ans);
return 0;
}
}
namespace Task2
{
void Output(__float128 ans)
{
printf("0.");
for(int i=1;i<=K;++i)
{
ans*=10;int x=(i==K)?(ans+0.5):ans;
printf("%d",x);ans-=x;
}
puts("");
}
int main()
{
static __float128 f[2][105][9005][3],ans;
f[0][0][py][0]=1;
for(int i=1,nw=1,pw=0;i<=n;++i,nw^=1,pw^=1)
{
memset(f[nw],0,sizeof(f[nw]));
for(int j=0;j<i;++j)
for(int k=0;k<=4500+py;++k)
for(int l=0;l<=2;++l)
if(f[pw][j][k][l])
{
if(k-i-i>=0)f[nw][j+1][k-i-i][l]+=f[pw][j][k][l]*(j+1-l);//一个新的连通块
if(j)f[nw][j][k][l]+=f[pw][j][k][l]*(j+j-l);//作为一个连通块的一端
if(j>=2&&k+i+i<=9000)f[nw][j-1][k+i+i][l]+=f[pw][j][k][l]*(j-1);//连接两个连通块
if(k-i>=0)f[nw][j+1][k-i][l+1]+=f[pw][j][k][l]*(2-l);//作为一个端点
if(j&&k+i<=9000)f[nw][j][k+i][l+1]+=f[pw][j][k][l]*(2-l);//一个连通块延伸到了边界
}
}
for(int i=M;i<=4500;++i)ans+=f[n&1][1][py+i][2];
for(int i=1;i<=n;++i)ans/=i;
Output(ans);
return 0;
}
}
int main()
{
scanf("%d%d%d",&n,&M,&K);
if(K<=8)Task1::main();
else Task2::main();
return 0;
}
05-02 02:45