JJ哥讓我幫他去看這道題，我順手A了，結果發現這題的耗時竟然排第一了。
d[i][1]表示從i點出發可以取得的最大值，d[i][0]則表示最小值，那么就有d[i][1]=max{ d[j][0] } + r[i]，d[i][0]=min{ d[j][1] } + r[i]，其中有一條<i,j>的邊。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/24 19:36:33
* File Name: hdu2452.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define Half(x) ((x)>>1)
#define Lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
bool scanf(int &num)
{
char in;
while((in=getchar())!=EOF && (in>'9' || in<'0'));
if(in==EOF) return false;
num=in-'0';
while(in=getchar(),in>='0' && in<='9') num*=10,num+=in-'0';
return true;
}
const int kMaxn(10007);
const int kMaxm(1000007);
int n,m,f,start,r[kMaxn],d[kMaxn][2];
int cnt,first[kMaxn],next[kMaxm],e[kMaxm];
bool into[kMaxn],out[kMaxn];
void Clear()
{
cnt=-1;
memset(first,-1,sizeof(first));
}
void AddEdge(int u,int v)
{
cnt++;
e[cnt]=v;
next[cnt]=first[u];
first[u]=cnt;
}
int dp(int u,int sign)
{
if(d[u][sign]!=-1)
return d[u][sign];
d[u][sign]=r[u];
int t(sign?0:kInf);
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i]);
if(sign)
t=max(t,dp(v,0));
else
t=min(t,dp(v,1));
}
d[u][sign]+=t;
return d[u][sign];
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("data.in","r",stdin);
#endif
while(scanf(n) && scanf(m) && scanf(f))
{
for(int i=1;i<=n;i++)
scanf(r[i]);
Clear();
memset(into,false,sizeof(into));
memset(out,false,sizeof(out));
while(m--)
{
int u,v;
scanf(u);
scanf(v);
AddEdge(u,v);
into[v]=true;
out[u]=true;
}
memset(d,-1,sizeof(d));
for(int i=1;i<=n;i++)
{
if(!out[i])
d[i][0]=d[i][1]=r[i];
else if(!into[i])
start=i;
}
if(dp(start,1)>=f)
printf("Victory\n");
else
printf("Glory\n");
}
return 0;
}
posted on 2011-08-24 19:58
lee1r 閱讀(431)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：動態規劃