暴力。
这怎么这么快。。。。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 505 #define inf 2000000000 using namespace std; int n,m,map[maxn][maxn],a[maxn][maxn],sum[maxn][maxn],ans=inf; bool vis[maxn][maxn]; bool gets(int x,int y) { int ret=0; for (register int i=1;i<=n;i++) for (register int j=1;j<=m;j++) { a[i][j]=map[i][j]; sum[i][j]=0; } for (register int i=1;i<=n;i++) for (register int j=1;j<=m;j++) { sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]; int now=a[i][j]+sum[i][j]; if (now<0) return false; if (now) { sum[i][j]-=now;sum[i+x][j]+=now; sum[i][j+y]+=now;sum[i+x][j+y]-=now; ret+=now; } } ans=min(ans,ret);return true; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&map[i][j]); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (gets(i,j)); printf("%d ",ans); return 0; }