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

发个代妈,很弱,813ms

Posted by KatrineYang at 2016-06-17 01:03:03 on Problem 1088
//============================================================================
// Name        : main1088.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

int hx[101][101];
int R, C;

int Max(int a, int b){
	if(a < b) return b;
	return a;
}

int partion(int *array, int p, int r) {
		int x = array[r];
		int i = p - 1;//注意这点,把i设成负值,然后作为移动的标志
		int j;
		for (j = p; j < r; j++) {
			if (hx[array[j]/C][array[j]%C] < hx[x/C][x%C]) {
				i++;
				int temp = array[j];
				array[j] = array[i];
				array[i] = temp;
			}
		}
		int temp = array[j];
		array[j] = array[i + 1];
		array[i + 1] = temp;
		return i+1;//返回的应该是交换后的哨兵的位置
}
		//递归解决每个划分后的小
void quickSort(int *array, int p, int r) {
		if (p < r) {
			int q = partion(array, p, r);
			quickSort(array, p, q - 1);
			quickSort(array, q + 1, r);
		}
}


int main() {
	//int R, C;

	cin >> R >> C;
	for(int i = 0; i < R; i++){
		for(int j = 0; j < C; j++){
			cin >> hx[i][j];
		}
	}
	int px[10001];
	for(int i = 0; i < R*C; i++) px[i] = i;
	quickSort(px, 0, R*C-1);
	//for(int i = 0; i < R*C; i++) cout << px[i] << " "; cout << endl;
	int maxi = 1;
	int res[101][101] = {{0}};
	for(int i = 0; i < R*C; i++){
		int row = px[i]/C, col = px[i]%C;
		bool isJBx = true;
		if(row != 0 && hx[row-1][col] < hx[row][col]){
			isJBx = false;
			res[row][col] = Max(res[row][col], res[row-1][col]+1);
		}
		if(col != 0 && hx[row][col-1] < hx[row][col]){
			isJBx = false;
			res[row][col] = Max(res[row][col], res[row][col-1]+1);
		}
		if(row != R-1 && hx[row+1][col] < hx[row][col]){
			isJBx = false;
			res[row][col] = Max(res[row][col], res[row+1][col]+1);
		}
		if(col != C-1 && hx[row][col+1] < hx[row][col]){
			isJBx = false;
			res[row][col] = Max(res[row][col], res[row][col+1]+1);
		}
		if(isJBx){
			res[row][col] = 1;
		}
		maxi = Max(maxi, res[row][col]);
		//cout << isJBx << " " << row << " " << col << " " << res[row][col] << endl;
	}
	cout << maxi << endl;
	//cout << "!!!Hello World!!!" << endl; // prints !!!Hello World!!!
	return 0;
}

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