夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

昨日今日の精進

プログラミング

PKU 2559

ヒストグラムの最大長方形を求める問題。
スタックで左端のアドレスと縦の長さを管理して求めます。

1964のついでに最大長方形の求め方を学ぶために通すつもりだったのですが、なぜか通らなかったので最終的に参考サイトのコードうつしました。
コメントアウトが自分のコードです。今回も何が違うのかわからないパターン(^_^;)

// #include <cstdio>
// #include <algorithm>
// #include <stack>
// using namespace std;
// typedef long long ll;

// struct Rectangle { int height; int pos; };

// ll getLargestRectangle(int size, ll buff[]) {
//     stack<Rectangle> S;
//     ll maxv = 0;
//     buff[size] = 0;
    
//     for (int i=0; i<=size; i++) {
//         Rectangle rect;
//         rect.height = buff[i];
//         rect.pos = i;
//         if (S.empty()) {
//             S.push(rect);
//         } else {
//             if (S.top().height < rect.height) {
//                 S.push(rect);
//             } else if (S.top().height > rect.height) {
//                 int target = i;
//                 while (!S.empty() && S.top().height >= rect.height) {
//                     Rectangle pre = S.top(); S.pop();
//                     ll area = pre.height * (i - pre.pos);
//                     maxv = max(maxv, area);
//                     target = pre.pos;
//                 }
//                 rect.pos = target;
//                 S.push(rect);
//             }
//         }
//     }
//     return maxv;
// }

// int main() 
// {
//     int s;
//     ll buff[110001];
    
//     while (scanf("%d", &s)&&s!=0) {
//         for (int i=0; i<s; i++) scanf("%lld", &buff[i]);
//         printf("%lld\n", getLargestRectangle(s, buff));
//     }
// }

// pku 2559 (Largest Rectangle in a Histogram)
// O(n) algorithm
#include<stdio.h>
#include<iostream>
#include<stack>
#include<algorithm>
#define MAX 110000
typedef long long llong;

using namespace std;

struct Rectangle{ llong height;  int pos; };
 
llong getRectangleArea( int size, llong buffer[]){
    stack<Rectangle> S;
    llong maxv = 0;
    buffer[size] = 0;
    
    for ( int i = 0; i <= size; i++ ){
        Rectangle rect;
        rect.height = buffer[i];
        rect.pos = i;
        if ( S.empty() ){
            S.push( rect );
        } else {
            if ( S.top().height < rect.height ){
                S.push( rect );
            } else if ( S.top().height > rect.height ) {
                int target = i;
                while ( !S.empty() && S.top().height >= rect.height){
                    Rectangle pre = S.top(); S.pop();
                    llong area = pre.height * (i - pre.pos);
                    maxv = max( maxv, area);
                    target = pre.pos;
                }
                rect.pos = target;
                S.push(rect);
            }
        }
     }
    
    return maxv;
 }

main(){
    int size;
    llong buffer[MAX+1];
    
    while(1){
        scanf("%d", &size);
        if ( size == 0 ) break;
        for ( int i = 0; i < size; i++ ) scanf("%lld", &buffer[i]);
        cout << getRectangleArea( size, buffer ) << endl;
    }
}

PKU 1964

先程の問題の応用。
一行一行をヒストグラムと考えて、二次元のマップ内での最大長方形を求める。

#include <cstdio>
#include <iostream>
#include <stack>
#include <algorithm>
#define MAX 1000
using namespace std;
struct rect 
{
    int height, pos;
};

int solve(int size, int buff[]) 
{
    stack<rect> S;
    int maxv = 0;
    buff[size] = 0;
    for (int i=0; i<=size; i++) {
        rect r;
        r.height = buff[i];
        r.pos = i;
        if (S.empty()) {
            S.push(r);
        }
        else {
            if (S.top().height < r.height) {
                S.push(r);
            }
            else if (S.top().height > r.height) {
                int target = i;
                while (!S.empty() && S.top().height >= r.height) {
                    rect pre = S.top();
                    S.pop();
                    int area = pre.height * (i - pre.pos);
                    maxv = max(maxv, area);
                    target = pre.pos;
                }
                r.pos = target;
                S.push(r);
            }
        }
    }
    return maxv;
}

int M, N;
char buff[MAX][MAX];
int T[MAX][MAX];

int solve2() 
{
    for (int i=0; i<M; i++) {
        for (int j=0; j<N; j++) {
            T[i][j] = 0;
        }
    }
    for (int j=0; j<N; j++) {
        int seq = 0;
        for (int i=0; i<M; i++) {
            if (buff[i][j] == 'R') {
                seq = T[i][j] = 0;
            }
            else {
                T[i][j] = ++seq;
            }
        }
    }
    
    int maxv = 0;
    for (int i=0; i<M; i++) {
        maxv = max(maxv, solve(N, T[i]));
    }
    
    return maxv;
}

int main() 
{
    int t;
    scanf("%d", &t);
    for (int ix=0; ix<t; ix++) {
        scanf("%d%d", &M, &N);
        for (int i=0; i<M; i++) {
            for (int j=0; j<N; j++) {
                cin >> buff[i][j];
            }
        }
        printf("%d\n", solve2()*3);
    }
}

PKU 2039

指定されたkeyの数だけ列ができるよう文章を縦書きし、蛇行して呼んだものを暗号としたときこれを復号する問題。
DPリストに書いてあったがやるだけ問題

#include <iostream>
#include <vector>
using namespace std;
int main() 
{
    int n;
    while (cin>>n&&n!=0) {
        string str;
        cin >> str;
        vector<string> map(str.length()/n, "");
        for (int i=0; i<str.length()/n; i++) {
            if (i % 2 == 0) {
                for (int j=i*n; j<i*n+n; j++) map[i] += str[j];
            }
            else {
                for (int j=(i+1)*n-1; j>=i*n; j--) map[i] += str[j];
            }
        }
        string res = "";
        for (int i=0; i<n; i++) for (int j=0; j<map.size(); j++)
                                    res += map[j][i];
        cout << res << endl;
    }
}

AOJ 0022

ちょっと手こずったが、kyuridenamidaさんにコーナーケース教えてもらって解決した感じの問題

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int main() 
{
    int n;
    while (scanf("%d", &n)&&n!=0) {
        long long int a[n];
        for (int i=0; i<n; i++) scanf("%lld", &a[i]);
        long long int dp[n];
        dp[0] = a[0];
        long long int res = dp[0];
        for (int i=1; i<n; i++) {
            dp[i] = max(a[i], dp[i-1]+a[i]);
            res = max(res, dp[i]);
        }
        printf("%lld\n", res);
    }
}

PKU 3903

LIS。蟻本で実装

#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;

int main() 
{
    int n;
    while (scanf("%d", &n)!=EOF) {
        int p[n];
        int dp[n];
        for (int i=0; i<n; i++) scanf("%d", &p[i]);
        fill(dp, dp+n, INT_MAX);
        for (int i=0; i<n; i++) {
            *lower_bound(dp, dp+n, p[i]) = p[i];
        }
        printf("%d\n", lower_bound(dp, dp+n, INT_MAX) - dp);
    }
}