Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

换一种思路:构造有向无环图,树形DP

Posted by uuuouou at 2014-12-12 13:56:15 on Problem 1036
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator