| ||||||||||
| 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 | |||||||||
WA了好多次了。。。//dp[i]表示以第i个结尾的所能得到的最大财产值,dp[i] = max(dp[j]+p_i) && T[i] - T[j] >= abs(S[i] - S[j]),数组已按时间排序
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 100
#define MAXK 100
#define MAXT 30000
int dp[MAXN + 1];
struct Gangster
{
int T, P, S;
Gangster(int tt = 0, int pp = 0, int ss = 0)
{
T = tt;
P = pp;
S = ss;
}
};
Gangster gangster[MAXN + 1];
int MyCompare(const void * e1, const void * e2)
{
return ((Gangster *)e1)->T - ((Gangster *)e2)->T;
}
int main()
{
int N, K, T;
scanf("%d %d %d", &N, &K, &T);
int i, j;
for (i = 0; i < N; i++) scanf("%d", &gangster[i].T);
for (i = 0; i < N; i++) scanf("%d", &gangster[i].P);
for (i = 0; i < N; i++) scanf("%d", &gangster[i].S);
qsort(gangster, N, sizeof(gangster[0]), MyCompare);
if (gangster[0].S < gangster[0].T) dp[0] = gangster[0].P;
else dp[0] = 0;
for (i = 1; i < N; i++)
{
int tempmax = 0;
bool flag = false;
for (j = 0; j < i; j++)
{
if (dp[j] != 0)//j被用到了
{
if (gangster[i].T == gangster[j].T && gangster[i].S != gangster[j].S) continue;
if (gangster[i].T - gangster[j].T >= abs(gangster[i].S - gangster[j].S + 0.0))
{
if (dp[j] + gangster[i].P > tempmax) tempmax = dp[j] + gangster[i].P;
}
flag = true;
}
}
if (!flag)
{
if (gangster[i].S <= gangster[i].T) dp[i] = gangster[i].P;
else dp[i] = 0;
}
else dp[i] = tempmax;
}
int ans = 0;
for (i = 0; i < N; i++)
{
if (dp[i] > ans) ans = dp[i];
}
printf("%d\n", ans);
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator