题目链接：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; }