ROBOCON - VOI 2012 Robocon

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1030
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

bool a[505][505] = {0},f[2][505][500] = {0},g[2][505][505] = {0};
int n,k,u,v;

int main(){
    
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
    scanf("%d %d",&n,&k);
    
    for(int ik = 0; ik < k; ik++){
        scanf("%d %d",&u,&v);
        a[u][v] = 1;
    }
    
    if(n == 1){
        printf("0");
        return 0;
    }
    
    g[0][1][0] = 1;
    g[1][n][0] = 1;
    int MIN = oo;
    
    for(int i = 1; i <= n; i++){
        memset(g,0,sizeof(g));
        for(int j = 1; j <= n; j++){
            if(i == 1 && j == 1) g[0][1][0] = 1;
            else if(!a[i][j]){
            for(int k = 0; k < j; k++) g[0][j][k] = f[0][j][k] | g[0][j-1][k-1] | f[0][j-1][k];
            }    
        }
        for(int j = n; j >=1; j--){
            if(i == 1 && j == n) g[1][n][0] = 1;
            else if(!a[i][j]){
                for(int k = 0; k < j; k++) g[1][j][k] = f[1][j][k] | g[1][j+1][k-1] | f[1][j+1][k];
            }
        }
        for(int j = 1; j <=n; j++){
            for(int k = 0; k < j; k++){
                f[0][j][k] = g[0][j][k];
                f[1][j][k] = g[1][j][k];
                if(f[0][j][k] && f[1][j][k]){
                   // printf("%d %d %d\n",i,j,k);
                    MIN = min(MIN,i + k - 1);
                } 
            }
        }
    }
    printf("%d\n",MIN);
}

Download