CREC01 – SPOJ

đề bài: http://vn.spoj.com/problems/CREC01/

Thuật toán:

• Bài này ta sử dụng kỹ thuật deque. Thuật toán cũng không có gì phức tạp. Bạn có thể đọc code bên dưới để hiểu thêm

Code:

Pascal:

const   fi      ='';
        fo      ='';
        oo      =1000;

var     a       :array[0..oo,0..oo] of 0..1;
        l,h,dem:array[0..oo+1] of int64;
        m, n    :longint;

procedure Optimize;
var     i, j    :longint;
        ans     :int64;
begin
        fillchar(h, sizeof(h),0);
        ans:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                begin
                                        if a[i,j]=1 then begin
                                        l[j]:=j;
                                        h[j]:=h[j]+1;
                                        while h[l[j]-1]>h[j] do
                                                l[j]:=l[l[j]-1];
                                        dem[j]:=h[j]*(j-l[j]+1)+dem[l[j]-1];
                                        ans:=ans+dem[j];
                                        //writeln(ans,'==');
                                        //if (i=3) and (j=2) then writeln(dem[1]);
                                        end
                                        else begin
                                                dem[j]:=0;
                                                l[j]:=0;
                                                h[j]:=0;
                                        end;

                                end;

                end;
        writeln(ans);
end;

procedure run;
var     i, j, tg    :longint;
        s       :ansistring;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                        readln(s);
                        for j:=1 to n do
                                        val(s[j],a[i,j]);
                end;
        Optimize;
        close(input);close(output);

end;

begin
        run;
end.

C++:

using namespace std;
#include

#define BG begin()
#define ED end()
#define st first
#define nd second
#define PB push_back
#define PF push_front
#define FOR(i,a,b) for (long long i=a;i=b; i--)
#define ri(n)({\
    int neg=0;\
    n=0;\
    char ch;\
    for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;\
    n=ch-48;\
    for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;\
    if (neg) n=-n;\
})

typedef long long ll;
typedef unsigned long long ull;
typedef pair II;
typedef pair LL;
const ll INF=1000000000+7;
const double esp=1e-13;
const double pi=3.141592653589;


ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];

int main()
{
    //freopen("CREC01.inp", "r", stdin);
    //freopen("CREC01.out", "w", stdout);
    cin>>m>>n;
    char ch;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            cin>>ch;
            a[i][j] = ch - '0';
        }
    memset(H, 0, sizeof(H));
    memset(L, 0, sizeof(L));
    memset(dem, 0, sizeof(dem));
    long long ans = 0;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            //cout< 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
                L[j] = k;
                dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
                ans += dem[j];
                //cout<