| ||||||||||
| 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