首页 > 代码库 > zoj 3367 Counterfeit Money(dp)
zoj 3367 Counterfeit Money(dp)
先搞定这题。ZOJ1985 Largest Rectangle in a Histogram
再做这题。先枚举第二个矩形对第一个矩形的偏移量(x,y),再进行2维DP,复杂度为O(n^2 *n^2),即O(n^4).
#include <bits/stdc++.h>using namespace std;const int maxn=42;int n1,m1,n2,m2;char a[maxn][maxn];char b[maxn][maxn];int dp[maxn][maxn];int L[maxn],R[maxn];int mx,u,v,w,z,rr,cc;bool inmaze(int i,int j){ return i>=0&&i<n2&&j>=0&&j<m2;}void DP(int r,int c){ memset(dp,0,sizeof dp); for(int i=0;i<n1;i++) for(int j=0;j<m1;j++){ if(inmaze(i+r,j+c)){ if(a[i][j]!=b[i+r][j+c])continue; if(i)dp[i][j]=dp[i-1][j]+1; else dp[i][j]=1; } } for(int i=0;i<n1;i++){ for(int j=0;j<m1;j++)L[j]=R[j]=j; for(int j=1;j<m1;j++){ int t=L[j]; while(t&&dp[i][t-1]>=dp[i][j])t=L[t-1]; L[j]=t; } for(int j=m1-2;j>=0;j--){ int t=R[j]; while(t<m1-1&&dp[i][t+1]>=dp[i][j])t=R[t+1]; R[j]=t; } for(int j=0;j<m1;j++){ if(!dp[i][j])continue; int res=dp[i][j]*(R[j]-L[j]+1); if(res>mx)mx=res,rr=dp[i][j],cc=R[j]-L[j]+1,v=L[j],u=i-dp[i][j]+1,w=u+r,z=v+c; } }}void run(){ for(int i=0;i<n1;i++)scanf("%s",a[i]); scanf("%d%d",&n2,&m2); for(int i=0;i<n2;i++)scanf("%s",b[i]); mx=0; for(int i=1-n1;i<n2;i++) for(int j=1-m1;j<m2;j++){ DP(i,j); } if(!mx)puts("0 0"); else printf("%d %d\n%d %d\n%d %d\n",rr,cc,u+1,v+1,w+1,z+1);}int main(){// freopen("in","r",stdin); while(scanf("%d%d",&n1,&m1)>0)run(); return 0;}
zoj 3367 Counterfeit Money(dp)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。