| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
简单的DP,一遍AC,贴代妈//============================================================================
// 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator