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