首页 > 代码库 > 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)