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#include <cstdio> #include <cstring> #include <cmath> #include <vector> #include <algorithm> using namespace std; int N, K, T; struct Node{ int t, s, p; bool operator < (const Node& other)const{ return t < other.t; } } node[101] = {0}; vector<int> out[101]; int gain[101]; bool input() { if(3 != scanf("%d%d%d", &N, &K, &T)) return false; for(int i = 1; i <= N; ++i) scanf("%d", &node[i].t); for(int i = 1; i <= N; ++i) scanf("%d", &node[i].p); for(int i = 1; i <= N; ++i) scanf("%d", &node[i].s); return true; } bool canBeSetUp(const Node& a, const Node& b) { return abs(b.s - a.s) <= abs(b.t - a.t); } void initGraph() { //sort up by time and remove all those come after close sort(node + 1, node + N + 1); while(node[N].t > T) --N; //build links for(int i = 0; i < N; ++i){ out[i].clear(); for(int j = i+1; j <= N; ++j){ if(canBeSetUp(node[i], node[j])) out[i].push_back(j); } } //initialize memset(gain, -1, sizeof(gain)); } int dp(int x) { if(gain[x] != -1) return gain[x]; gain[x] = node[x].p; const vector<int>& v = out[x]; if(!v.empty()){ int tmp = 0; for(int i = v.size()-1; i > -1; --i){ tmp = max(tmp, dp(v[i])); } gain[x] += tmp; } return gain[x]; } int main() { while(input()){ initGraph(); printf("%d\n", dp(0)); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator