植物大战僵尸(pvz)_植物大战僵尸复杂度

植物大战僵尸

题解

写这道题的过程贞德好艰辛呀。

很容易发现一个结论，如果我们把每个转化，如果所有的总和大于等于1，就一定有解。

因为如果这样的话，我们一定可以找出一种方法将两条路分成两个权值使得两边都不小于，除非你有一只僵尸跑到别人家里去了。而此时它肯定会选择其中一行全部消灭掉，我们还剩一行权值不小于，它们前进后得到的权值一定会不小于，不断重复这个过程，我们就得到必胜的策略。

这样，第一个问题就解决了，我们接下来思考如何求出第一次策略的数量，就是将所有分成两个的方案数。

考虑容斥，答案就是总方案数减去两个分出一个小于的方案数。

我们可以定义表示到了第个人这里，还差个次方达到。状态转移方程式也很好推，

$dp_{i,j}=dp_{i-1,\frac{j}{2^{a_{i}-a_{i-1}}}}+dp_{i-1,\frac{j+1}{2^a_{i}-a_{i-1}}}$。

特别地，如果差的数量已经超过了剩余的数量，就不需要继续下去，直接加入答案，这样就只需要将的第二维减小到了。

总的时间复杂度。

源码

有些卡常。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
#define MAXN 2005
typedef long long LL;
const int mo=1e9+7;
const double eps=1e-7;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
int add(int x,int y){return x+y>=mo?x+y-mo:x+y;}
int dp[MAXN][MAXN],n,a[MAXN],pow2[MAXN],t;
double sum;
signed main(){
	pow2[0]=1;for(int i=1;i<=2e3;i++)pow2[i]=2ll*pow2[i-1]%mo;read(t);
	while(t--){
		read(n);sum=0;int tmp=0;
		for(int i=1;i<=n;i++)read(a[i]),sum+=1.0/(1.0*pow2[a[i]]);
		if(sum<1.0-eps){puts("0");continue;}
		sort(a+1,a+n+1);dp[0][1]=1;a[0]=1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++){
				int tp=a[i]-a[i-1];if(j==((j>>tp)<<tp))dp[i][j]=dp[i-1][j>>tp];
				if(j+1==((j+1>>tp)<<tp))dp[i][j]=add(dp[i][j],dp[i-1][j+1>>tp]);
				if(j>(n-i))tmp=add(tmp,1ll*dp[i][j]*pow2[n-i]%mo),dp[i][j]=0;
				//printf("%d %d:%d %d\n",i,j,dp[i][j],dp[i-1][j/pow2[a[i]-a[i-1]]]);
			}
		int ans=(pow2[n]-tmp*2ll%mo+mo)%mo;printf("%d\n",ans);
		if(t>0)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=0;
	}
	return 0;
}

谢谢！！！