zkx06111's Blog

//O(n^2)动态规划,f[i][j]前后分别表示以(i,j)为右下角的最多条数
//预处理出数组r[i][j]前后分别表示(i,j)左边和右边鱼的条数
//rn[i][j]表示(i,j)上方鱼的条数
//为了省空间只好回收利用数组了。。。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int ans=0,n,m,f[2505][2505];
unsigned short r[2505][2505],rn[2505][2505],pond[2505][2505];
int main(){
	scanf("%d%d",&n,&m);
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			scanf("%d",&pond[i][j]);
			r[i][j]=r[i][j-1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	for (int j=1;j<=n;++j)
		for (int i=1;i<=m;++i){
			rn[j][i]=rn[j-1][i]+pond[j][i];
			//printf("rm%d,%d=%d\n",j,i,rn[j][i]);
		}
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][1]=pond[j][1];
	
	for (int i=1;i<=n;++i)
		for (int j=1;j<=m;++j){
			if (i==1 || j==1){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (r[i][j-1]==r[i][j-f[i-1][j-1]-1]
				&& rn[i-1][j]==rn[i-f[i-1][j-1]-1][j])
				f[i][j]=f[i-1][j-1]+1;
			//printf("f%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	memset(f,0,sizeof(f));
	
	for (int i=1;i<=m;++i) f[1][i]=pond[1][i];
	for (int j=1;j<=n;++j) f[j][m]=pond[j][m];
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			r[i][j]=r[i][j+1]+pond[i][j];
			//printf("r%d,%d=%d\n",i,j,r[i][j]);
		}
	
	for (int i=1;i<=n;++i)
		for (int j=m;j>0;--j){
			if (i==1 || j==m){
				ans=max(ans,f[i][j]);
				continue;
			}
			if (pond[i][j]==0){
				f[i][j]=0;
				continue;
			}
			f[i][j]=1;
			if (i==2 && j==3) {
				//printf("  %d,%d=%d\n",i-1,j,rn[i-1][j]);
				//printf("  %d,%d=%d\n",i-g[i-1][j+1]-1,j,rn[i-g[i-1][j+1]-1][j]);
			}
			if (r[i][j+f[i-1][j+1]+1]==r[i][j+1]
				&& rn[i-1][j]==rn[i-f[i-1][j+1]-1][j]){
				//printf("!!%d,%d!!\n%d,",i,j,f[i-1][j+1]);
				f[i][j]=f[i-1][j+1]+1;
			}	
			//printf("g%d,%d=%d\n",i,j,f[i][j]);
			ans=max(ans,f[i][j]);
		}
	
	printf("%d",ans);
	
	return 0;
}

#include <iostream>
#include <climits>
using namespace std;

long long h[51],b[51]={1};
int n,f[51];

int main()
{
	cin>>n;
	for (int i=1;i<=n;++i){
		cin>>h[i];
		b[i]=b[i-1]<<1;
	}
	for (int i=2;i<=n;++i){
		f[i]=INT_MAX/3;
		for (int j=1;j<i;++j)
			for (int k=j;k>0;--k)
				if (b[j-k]+h[k]>=h[i])
					f[i]=min(f[j]+j-k+1,f[i]);
		if (f[i]==INT_MAX/3){
			cout<<-1;
			return 0;
		}
		//cout<<i<<'='<<f[i]<<endl;
	}
	cout<<f[n];
	return 0;
}

//参考了别人的代码，这种头尾相接的处理十分巧妙
#include <iostream>
using namespace std;
int n,m,f[32][32]; //f[i][j]表示第i次j拿到球的种数
int main()
{
	cin>>n>>m;
	f[0][1]=f[0][n+1]=1; //初始化，头和尾接上
	for (int i=1;i<=m;++i) {
		for (int j=1;j<=n;++j)
			f[i][j]=f[i-1][j-1]+f[i-1][j+1];
		f[i][0]=f[i][n]; f[i][n+1]=f[i][1]; //再次处理头尾
	}
	cout<<f[m][1];
	return 0;
}