UCF Local Prograamming Contect 2019 Sub Matrix Sum

Sub Matrix Sum
You have written many programs to search mazes so matrix search shoudn't be any different、or will it?
The Problem:An integer marix with R rows and C columns has写真1.png sub marices.We want to select a sub matrix with sum(the sum of all integers in it)greater than or equal to a givent integer S.Wezathe the the the the the the thethethethethe aaaaaaaaazzzzzzaaaaaaaaathethethethethethethethethethethethethe thethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethethetheelements in that sub matrix(i.e.number of rows*number of columns in that sub matrix)
The Input:The first input line consists of three integers R、C(1≦R≦100,000;1≦C≦100,000;1≦R*C≦100,000)and S.Next R lins s containininininininininption of the matix.Each of these se se se se se se ininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininintx.Eaax.Alax.Each.Each.Each.Alach.and+10^910 9,inclusive.
The Output:Print the size of the minimum sub marix whose sum is greater or equal to the given S.If there isのsuch sub matrix,output-1.
サンプル入力1コピー3 26-1 3 3 4-5 6 7 9サンプル出力1コピー4サンプル入力2コピー3 0-1-2-3-4-5-6-7-9サンプル出力2コピー-1サンプル入力3コピー2-1-1-2サンプル出力3コピー1
テーマ:行列を提供して、彼のサブマトリックスを探し出して、彼の和がSに等しくなるようにします.そして、サブマトリックスをできるだけ小さくして、まずデータ範囲を見るとおかしいです.暴力は、肯定的に行われ、二桁のプレフィックスと時間の複雑さを加えて二次元に引き下げられます.正しい解法は:

は、既存の列と2ビットのプレフィックスと

を処理する.

は次に2行を列挙し、(開始行と終了行)sum[k]=v[j]-v[i-1]sum[k]+=sum[k-1]という2行の間のデータを列に従って1行に圧縮した

.

は次に、この行において、一連のシーケンスの和を探し、S以上であり、かつ、できるだけ小さい

を指す.

スライドウィンドウもよく分かりますが、スライドウィンドウに負の数がないと単調なスタックに行くしかないということを忘れてしまいました.

具体的な実装コード

を参照してください.

#include 
#include 
#include 
#include 
#include 
#include 
//                                    ，     3    
//          
using namespace std;
#define Maxn 100005
const int INF = 0x3f3f3f3f;
#define  LL long long
vector<vector<LL> > v;
vector<LL> st;//    
LL sum[Maxn],s;
int r,c;

int Solve() {// c lie
    int res = INF;
    st.clear(); st.push_back(0);
    for(int i=1; i<=c; i++) {
        int l = 0,r = st.size() - 1;
        LL tmp = sum[i] - s;
        int Ans = -1;
        while(l <= r) {
            int Mid = l + r >> 1;
            if(sum[st[Mid]] <= tmp) {
                l = Mid + 1;
                Ans = st[Mid];
            }
            else r = Mid - 1;
        }
        if(Ans != -1) res = min(res,i - Ans);
        while(!st.empty() && sum[st[st.size() - 1]] >= sum[i]) st.pop_back();
        st.push_back(i);
    }
    if(res == INF) res = -1;
    return res;
}

int main(int argc,char* argv[]) {
    int T ; scanf("%d",&T);
    while(T--) {
        scanf("%d %d %lld",&r,&c,&s);
        v.clear();
        if(r < c) {
            v.resize(r + 1);
            for(int i=0; i<=r; i++) v[i].resize(c + 1);
            for(int i=1; i<=r; i++)
                for(int j=1; j<=c; j++) scanf("%lld",&v[i][j]);
        } else {
            v.resize(c + 1);
            for(int i=0; i<=c; i++) v[i].resize(r + 1);
            for(int i=1; i<=r; i++)
                for(int j=1; j<=c; j++) scanf("%lld",&v[j][i]);
            swap(c,r);
        }
        //      r     c     r《c
        for(int i=0; i<=c; i++) v[0][i] = 0;
        for(int i=1; i<=r; i++)
            for(int j=1; j<=c; j++)
                v[i][j] = v[i - 1][j] + v[i][j];
        int Ans = r * c + 1;
        for(int i=1; i<=r; i++)
            for(int j=i; j<=r; j++) {//             i、j    
                sum[0] = 0;
                for(int k=1; k<=c; k++) sum[k] = v[j][k] - v[i -1][k];// i j        
                for(int k=1; k<=c; k++) sum[k] += sum[k - 1];
                int ret = Solve();
                if(ret == -1) continue;
                else Ans = min(Ans,ret * (j - i + 1));
            }
        if(Ans == r * c + 1) printf("-1
");
        else printf("%d
",Ans);
    }


    return 0;
}