boj 20641. Sleeping Cows

www.acmicpc.net/problem/20641

 

USACO 문제입니다.

 

 

Dynamic programming 으로 해결할 수 있는 문제입니다.

 

문제 해결 관찰)

 

1. $ s_{j} $ 가 $ t_{i} $ 안에 배정되는 모든 barn 의 크기를 오름차순 시키고 배정할 때 괄호문자열처럼 되어야 합니다.

   $ s_{i} $ 는 (

   $ t_{i} $ 는 ) 

 

2. 배정되지 못한 barn 들은 $ max(t_{i}) $ < $ min(s_{i}) $ 를 만족해야 합니다. 즉 $ t_{i} $ 가 쭉 주어지다 $ s_{i} $ 가 주어져야 합니다.

 

주어진 $ s_{i} $ 와 $ t_{i} $ 를 모두 합쳐서 정렬을 합니다 ( $ s_{i} $ 와 $ t_{i} $ 의 값이 같다면 $ s_{i} $ 가 먼저 오도록 한다 )

 

그리고 $ dp[i][j][t] $ 배열을 선언합니다.

 

$ dp[i][j][t] $ 에서

$ i $ 는 배정되는 모든 barn 의 괄호문자열 값이고 ( $ s_{i} $ 면 + $ t_{i} $ 면 - )

$ j $ 는 배정되지 못한 barn 의 값 ( $ t_{i} $ 면 + $ s_{i} $ 면 - )

$ t $ 는 배정되지 못한 barn 의 타입 ( $ t_{i} $ 가 진행중이면 0 $ s_{i} $  진행중이면 1 )

 

 

그럼 문제가 생깁니다. 이렇게 진행하면 시간복잡도가 $ N^{3} $ 이 아닐까요?

 

근데 좀 들여다보면 $ i $ 배열에서는 $ s_{i}  - t_{i} $ 고 $ j $ 배열에선 $ t_{j} - s_{j} $ 입니다.

즉 $ i $ - $ j $ 를 하면 $ s_{i} + s_{j} - ( t_{i} + t_{j} ) $  이기 때문에 $ i $ 값이 정해지면 $ j $ 값도 정해지게 됩니다.

 

즉 이를 이용하면 $ N^{2} $ 시간복잡도에 해결할 수 있습니다.

 

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pi;
typedef pair<lld,lld> pl;
typedef pair<int,lld> pil;
typedef pair<lld,int> pli;
typedef vector<int> vit;
typedef vector<vit> vitt;
typedef vector<lld> vlt;
typedef vector<vlt> vltt;
typedef vector<pi> vpit;
typedef vector<vpit> vpitt;
typedef long double ld;
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(), v.end()
#define sz(x) (int)x.size()
#define mk(a,b) make_pair(a,b)
bool isrange(int y,int x,int n,int m){
     if(0<=y&&y<n&&0<=x&&x<m) return true;
     return false;
}
int dy[4] = {1,0,-1,0},dx[4]={0,1,0,-1},ddy[8] = {1,0,-1,0,1,1,-1,-1},ddx[8] = {0,1,0,-1,1,-1,1,-1};
 
const lld mod = 1e9 + 7;
const int MAX = 3030;
lld dp[MAX][MAX][2];
vector<pi> v;
bool tmr(pi a,pi b){
    if(a.x!=b.x) return a.x < b.x;
    return a.y < b.y;
}
void solve(int tc){
    int n;
    scanf("%d",&n);
    for(int e=1;e<=n;e++){
        int r;
        scanf("%d",&r);
        v.push_back(mk(r,0));
    }
    for(int e=1;e<=n;e++){
        int r;
        scanf("%d",&r);
        v.push_back(mk(r,1));
    }
    sort(all(v),tmr);
    dp[0][0][0] = 1;
    int tot = 0;
    for(int e=0;e<sz(v);e++){
        int ty = v[e].y;
        if(ty==0){
            for(int q=0;q<=n;q++){
                int r = q - (tot+1);
                if(r>=0) dp[q][r][0] = dp[q][r][1] = 0;
            }
        }else{
            for(int q=0;q<=n;q++){
                int r = q - (tot-1);
                if(r>=0) dp[q][r][0] = dp[q][r][1] = 0;
            }
        }
        for(int q=0;q<=n;q++){
            int r = q - tot;
            if(r<0) continue;
            if(ty==0){
                dp[q+1][r][0] = (dp[q+1][r][0]+dp[q][r][0]*(q+1))%mod;
                dp[q+1][r][1] = (dp[q+1][r][1]+dp[q][r][1]*(q+1))%mod;
                if(r) dp[q][r-1][1] = (dp[q][r-1][1]+dp[q][r][0]+dp[q][r][1])%mod;
            }else{
                if(q){
                    dp[q-1][r][0] = (dp[q-1][r][0]+dp[q][r][0])%mod;
                    dp[q-1][r][1] = (dp[q-1][r][1]+dp[q][r][1])%mod;
                }
                dp[q][r+1][0] = (dp[q][r+1][0]+dp[q][r][0])%mod;
            }
        }
        if(ty==0) tot++;
        else tot--;
    }
    lld ans = (dp[0][0][0]+dp[0][0][1])%mod;
    printf("%lld\n",ans);
}
 
 
int main(void){
 
//    ios_base :: sync_with_stdio(false);
//    cin.tie(NULL);
//    cout.tie(NULL);
 
    int tc = 1;
    /*
        cin >> tc;
    */
    for(int test_number=1;test_number<=tc;test_number++){
        solve(test_number);
    }
    return 0;
}