hihoCoder Challenge 27 #1469 : 福字 dp

点击打开链接

思路：

dp[i][j]表示以第i行第j列元素为矩阵右下角所能得到的最大福字的大小。

对于这一个矩阵, dp[i][j]对于dp[i][j-1]来说属于竖向扩充。

同理，dp[i][j]对于dp[i-1][j]来说属于横向扩充。

所以

if(a[i-1][j]==a[i][j]-1 && a[i][j-1]==a[i][j]-1) 				dp[i][j] = dp[i-1][j-1]+1;
其他条件便只能由所在一个元素去构成一个福字矩阵了，大小是1。
数据弱 AC了 但是想了想 
31 1 11 2 31 3 4就是错的 答案应该是2。。。
代码：
#include <bits/stdc++.h>using namespace std;int a[1005][1005],dp[1005][1005];int main(){	int n; cin>>n;	for(int i=1; i<=n; i++)		for(int j=1; j<=n; j++)			cin >> a[i][j];	for(int i=1; i<=n; i++)		for(int j=1; j<=n; j++)			dp[i][j] = 1;	int ans = 0;	for(int i=1; i<=n; i++)		for(int j=1; j<=n; j++){			if(a[i-1][j]==a[i][j]-1 && a[i][j-1]==a[i][j]-1) 				dp[i][j] = dp[i-1][j-1]+1;			ans = max(ans,dp[i][j]);		}	cout << ans << endl;	}
正解：
设 dp[i][j] 为以 i，j 位置为正方形右下角点所能构成的满足条件得到最大正方形，同时 用 up[i][j] 表示以 i，j 位置为最底部向上能连续满足条件的位置个数，用 lf[i][j] 表示以 i，j 位置为最右端向左能连续满足条件的位置个数。
转移: 
if(mp[i][j] == mp[i-1][j-1]+2)				dp[i][j] = min(min(up[i][j],lf[i][j]), dp[i-1][j-1]+1);代码：
#include <bits/stdc++.h>using namespace std;const int maxn = 1005;int n;int mp[maxn][maxn];int dp[maxn][maxn];int up[maxn][maxn];int lf[maxn][maxn];int main(){	scanf("%d", &n);	int ans = 0; 	for(int i=1;i<=n;i++){		for(int j=1;j<=n;j++){ 			scanf("%d", &mp[i][j]);			if(mp[i][j] == mp[i][j-1]+1) 				lf[i][j] = lf[i][j-1]+1;			else 				lf[i][j] = 1;			if(mp[i][j] == mp[i-1][j]+1) 				up[i][j] = up[i-1][j]+1;			else 				up[i][j] = 1;			if(mp[i][j] == mp[i-1][j-1]+2)				dp[i][j] = min(min(up[i][j],lf[i][j]), dp[i-1][j-1]+1);			else				dp[i][j] = 1;			ans = max(ans,dp[i][j]);		} 	}  	PRintf("%d/n", ans);}