BZOJ4621 Tc605（动态规划）

　　容易发现最终序列所有数字的相对顺序不变，一个数字可能的覆盖范围由两边第一个比它大的数决定，且若不考虑次数限制所有这样的序列都可以变换得到。对于一个序列，其需要的最少变换次数显然就是覆盖了别的位置的数的种数。于是设f[i][j][k][0/1]为第i位填了第j个数时以最优策略操作了k次，第i-1为是否填j时，变换方案数。转移考虑这一步填j是否要额外增加操作次数即可。暴力dpO(n⁴)，前缀和优化O(n³)。

　　半年之后终于会做了，可喜可贺。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 510

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}

int gcd(int n,int m){return m==0?n:gcd(m,n%m);}

int read()

{

	int x=0,f=1;char c=getchar();

	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}

	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

	return x*f;

}

int n,m,a[N],pre[N],nxt[N],f[2][N][N][2],g[N][N];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int main()

{

#ifndef ONLINE_JUDGE

	freopen("bzoj4621.in","r",stdin);

	freopen("bzoj4621.out","w",stdout);

	const char LL[]="%I64d\n";

#else

	const char LL[]="%lld\n";

#endif

	n=read(),m=read();

	for (int i=1;i<=n;i++) a[i]=read();

	for (int i=1;i<=n;i++)

	{

		for (pre[i]=i;pre[i]>1&&a[pre[i]-1]<a[i];pre[i]--);

		for (nxt[i]=i;nxt[i]<n&&a[nxt[i]+1]<a[i];nxt[i]++);

	}

	f[0][0][0][0]=1;

	for (int j=1;j<=n;j++)

	{

		memset(f[j&1],0,sizeof(f[j&1]));

		for (int i=0;i<=n;i++)

			for (int k=0;k<=m;k++)

			g[i][k]=((i?g[i-1][k]:0)+(f[j&1^1][i][k][0]+f[j&1^1][i][k][1])%P)%P;

		for (int i=1;i<=n;i++)

		if (pre[i]<=j&&nxt[i]>=j)

			for (int k=0;k<=m;k++)

			{

				if (k>=(i!=j)) inc(f[j&1][i][k][0],g[i-1][k-(i!=j)]);

				if (k>=(j-1==i)) inc(f[j&1][i][k][1],f[j&1^1][i][k-(j-1==i)][0]);

				inc(f[j&1][i][k][1],f[j&1^1][i][k][1]);

			}

	}

	int ans=0;

	for (int i=1;i<=n;i++)

		for (int k=0;k<=m;k++)

		inc(ans,f[n&1][i][k][0]),inc(ans,f[n&1][i][k][1]);

	cout<<ans;

	return 0;

}

秒客网

BZOJ4621 Tc605（动态规划）

相关文章