Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

AC代码,动规

Posted by zxj1015 at 2015-05-05 22:54:11 on Problem 3018
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <stack>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;

const int MAX_N = 510;
const int MAX_D = 1010;

int boxes[MAX_N][MAX_D];
int max_num[MAX_N];

vector<int> graph[MAX_N];

inline bool CanPut(int i, int j, int D) {
  for (int k = 0; k < D; ++k) {
    if (boxes[i][k] >= boxes[j][k]) {
      return false;
    }
  }
  return true;
}

int Dfs(int start) {
  if (max_num[start] >= 0) {
    return max_num[start];
  }
  int max_v = 0;
  for (int i = 0; i < graph[start].size(); ++i) {
    int succ = graph[start][i];
    int num = Dfs(succ);
    if (num > max_v) {
      max_v = num;
    }
  }
  return max_num[start] = max_v + 1;
}

int main() {
  int N, D;
  while (scanf("%d %d", &N, &D) != EOF) {
    for (int i = 0; i <= N; ++i) {
      for (int j = 0; j < D; ++j) {
        scanf("%d", &boxes[i][j]);
      }
      sort(boxes[i], boxes[i] + D);
    }
    for (int i = 0; i <= N; ++i) {
      graph[i].clear();
    }
    for (int i = 0; i <= N; ++i) {
      for (int j = i + 1; j <= N; ++j) {
        if (CanPut(i, j, D)) {
          graph[i].push_back(j);
        } else if (CanPut(j, i, D)) {
          graph[j].push_back(i); // 刚开始这里漏了,WA了一次
        }
      }
    }
    memset(max_num, -1, sizeof(max_num));
    int num = Dfs(0);
    if (num == 1) {
      printf("Please look for another gift shop!\n");
    } else {
      printf("%d\n", num - 1);
    }
  }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator