题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5749
参考文章:http://m.blog.csdn.net/article/details?id=52020617
题目要求求出这个公式的值,首先来看S(a,b),其实对于一个矩阵,可以手动画一下,一个矩阵的鞍点至多只有一个,那么s(a,b)其实就是矩阵中这个鞍点的值,那么如何来求鞍点。
如果一个点能成为某个矩阵的鞍点,按题目所说,那么这个点的左右的点都比这个点大,上下的点都比这个点小,那么对于一个点就是要求出最长这个点可以把四个边延长多长,u,d,l,r。用单调栈的处理可以快一点,不知道暴力处理能不能过。
处理出来好后,因为一个矩阵最多只有一个这样的鞍点,那么,就是枚举每个点,它能成为多少个矩阵的鞍点,因为已经知道一个点作为鞍点所能构成的最大矩阵,那么在这个矩阵内部且包含该点的都是满足条件的矩阵。然后原来的公式呢其实就是枚举每一个这样的矩阵加起来。具体化解可以看这里http://m.blog.csdn.net/article/details?id=52020617
#include<iostream> #include<cstdio> #include<map> #include<cstring> #include<string> #include<stack> #include<queue> #include<algorithm> #include<cmath> #include<vector> using namespace std; #define LL long long LL u[1005][1005]; LL d[1005][1005]; LL l[1005][1005]; LL r[1005][1005]; LL dat[1005][1005]; int n,m; void Left() { for(int i = 0;i<n;i++) { stack<pair<int,int> >sta; for(int j = 0;j<m;j++) { if(sta.empty()) { pair<int,int> temp; temp.first = dat[i][j]; temp.second = j; sta.push(temp); l[i][j] = 1; } else { while(!sta.empty() && sta.top().first>dat[i][j]) { sta.pop(); } if(sta.empty()) { l[i][j] = j+1; } else l[i][j] = j-sta.top().second; pair<int,int>temp; temp.first = dat[i][j]; temp.second = j; sta.push(temp); } } } } void Right() { for(int i = 0;i<n;i++) { stack<pair<int,int> >sta; for(int j = m-1;j>=0;j--) { if(sta.empty()) { pair<int,int> temp; temp.first = dat[i][j]; temp.second = j; sta.push(temp); r[i][j] = 1; } else { while(!sta.empty() && sta.top().first>dat[i][j] ) { sta.pop(); } pair<int,int>temp; if(sta.empty()) r[i][j] = m-j; else r[i][j] = sta.top().second-j; temp.first = dat[i][j]; temp.second = j; sta.push(temp); } } } } void UP() { for(int j = 0;j<m;j++) { stack<pair<int,int> >sta; for(int i = 0;i<n;i++) { if(sta.empty()) { pair<int,int> temp; temp.first = dat[i][j]; temp.second = i; sta.push(temp); u[i][j] = 1; } else { //cout << "666"; while(!sta.empty() && sta.top().first<dat[i][j] ) { sta.pop(); } if(sta.empty()) { u[i][j] = i+1; } else u[i][j] = i-sta.top().second; pair<int ,int> temp; temp.first = dat[i][j]; temp.second = i; sta.push(temp); } } } } void Down() { for(int j = 0;j<m;j++) { stack<pair<int,int> >sta; for(int i = n-1;i>=0;i--) { if(sta.empty()) { pair<int,int> temp; temp.first = dat[i][j]; temp.second = i; sta.push(temp); d[i][j] = 1; } else { while(!sta.empty() && sta.top().first<dat[i][j]) { sta.pop(); } if(sta.empty()) { d[i][j] = n-i; } else d[i][j] = sta.top().second-i; pair<int ,int> temp; temp.first = dat[i][j]; temp.second = i; sta.push(temp); } } } } void Print(LL arr[][1005]) { for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { printf("%4lld",arr[i][j]); } printf("\n"); } } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { scanf("%lld",&dat[i][j]); } } // 左边界 Left(); Right();//printf("123"); UP(); Down(); LL ans = 0; for(int i = 0;i<n;i++) { for(int j = 0;j<m;j++) { LL temp = (l[i][j]*r[i][j]*u[i][j]*d[i][j])*(l[i][j]+r[i][j])*(u[i][j]+d[i][j]); temp *= dat[i][j]; temp /= 4; temp %= (1ll<<32); ans += temp; ans %= (1ll<<32); } } printf("%lld\n",ans); } return 0; }