题意：
给出一个DAG，每个点上有一定的价值p和数量w,给出一些转换关系：a
i-1 a
i b
i ，即a
i-1可以兑换成b
i单位a
i ,然后问这些点的最大价值。
解法：
由于是DAG，可以用DP来解，dp[pos]=max{p[pos],dp[k]*rate[pos][k]},g[pos][k]=true
然后结果就是sum{dp[i]*w[i]}
这次第一次参加regional，fzu现场赛时候各种手残脑残，N个能够秒的题都没去看。甚可惜。。。回来看了下题目都不是多困难的，做个5题没问题的说。。。哎，明年再一雪耻辱吧。。
代码：
1
# include <cstdio>
2# include <vector>
3using namespace std;
4const int N=10005;
5struct node
6
{
7
int nxt;
8 double rate;
9
node(int n,double r):nxt(n),rate(r){};
10
};
11vector<node> g[N];
12double p[N],w[N];
13bool used[N];
14int n;
15void solve(int pos)
16{
17 if(used[pos]) return;
18 used[pos]=true;
19 for(int i=0;i<g[pos].size();i++)
20 {
21 solve(g[pos][i].nxt);
22 if(g[pos][i].rate*p[g[pos][i].nxt]>p[pos]) p[pos]=g[pos][i].rate*p[g[pos][i].nxt];
23
}
24}
25int main()
26{
27 while(true)
28 {
29 scanf("%d",&n);
30 if(!n) break;
31 for(int i=1;i<=n;i++)
32 {
33 scanf("%lf%lf",p+i,w+i);
34 g[i].clear();
35 used[i]=false;
36 }
37 int m;
38 scanf("%d",&m);
39 while(m--)
40 {
41 int k;
42 scanf("%d",&k);
43 int last,now;
44 scanf("%d",&last);
45 k--;
46 while(k--)
47 {
48 double r;
49 scanf("%lf%d",&r,&now);
50 g[last].push_back(node(now,r));
51 last=now;
52 }
53 }
54 for(int i=1;i<=n;i++)
55 solve(i);
56 double ans=0;
57 for(int i=1;i<=n;i++)
58 ans+=p[i]*w[i];
59 printf("%.2f\n",ans);
60 }
61 return 0;
62}
63