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

简单的DP,一遍AC,贴代妈

Posted by KatrineYang at 2016-06-08 21:20:16 on Problem 1036
//============================================================================
// Name        : main1036.cpp
// Author      : 
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
using namespace std;

const int MIN_INT = -2147483648;

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

int maxi(int a, int b){
	if(a>b) return a;
	return b;
}

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



int main() {
	int N, K, T;
	cin >> N >> K >> T;
	int t[101] = {0}, p[101] = {0}, s[101] = {0};
	for(int i = 1; i <= N; i++) cin >> t[i];
	for(int i = 1; i <= N; i++) cin >> p[i];
	for(int i = 1; i <= N; i++) cin >> s[i];
	quickSort(t, p, s, 1, N);
	//for(int i = 1; i <= N; i++) cout << t[i] << " " << p[i] << " " << s[i] << endl;
	int moments[101] = {0};
	int minindex[102] = {0};
	int cnt = 0;
	int tag = 0;
	for(int i = 1; i <= N; i++){
		if(t[i] == tag) continue;
		tag = t[i];
		moments[cnt+1] = t[i];
		minindex[cnt+1] = i;
		cnt++;
	}
	minindex[cnt+1] = N+1;
	//for(int i = 1; i <= cnt; i++) cout << moments[i] << " ";
	int maxPros[101][101];
	maxPros[0][0] = 0;
	for(int i = 1; i <= K; i++){
		maxPros[0][i] = MIN_INT;
	}
	for(int i = 1; i <= cnt; i++){
		int timeDif = moments[i] - moments[i-1];
		int tempPros[101] = {0};
		for(int j = minindex[i]; j < minindex[i+1]; j++){
			tempPros[s[j]] += p[j];
		}
		for(int j = 0; j <= K; j++){
			int lower = maxi(0, j-timeDif);
			int upper = mini(K, j+timeDif);
			int mx = MIN_INT;
			for(int k = lower; k <= upper; k++){
				mx = maxi(mx, maxPros[i-1][k]);
			}
			if(mx < 0) mx = MIN_INT;
			else mx += tempPros[j];
			maxPros[i][j] = mx;
		}
	}
	int mxx = MIN_INT;
	for(int i = 0; i <= K; i++) mxx = maxi(mxx, maxPros[cnt][i]);
	if(mxx < 0) mxx = 0;
	cout << mxx << 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