題意：
給出一個(gè)DAG，每個(gè)點(diǎn)上有一定的價(jià)值p和數(shù)量w,給出一些轉(zhuǎn)換關(guān)系：a
i-1 a
i b
i ，即a
i-1可以?xún)稉Q成b
i單位a
i ,然后問(wèn)這些點(diǎn)的最大價(jià)值。
解法：
由于是DAG，可以用DP來(lái)解，dp[pos]=max{p[pos],dp[k]*rate[pos][k]},g[pos][k]=true
然后結(jié)果就是sum{dp[i]*w[i]}
這次第一次參加regional，fzu現(xiàn)場(chǎng)賽時(shí)候各種手殘腦殘，N個(gè)能夠秒的題都沒(méi)去看。甚可惜。。。回來(lái)看了下題目都不是多困難的，做個(gè)5題沒(méi)問(wèn)題的說(shuō)。。。哎，明年再一雪恥辱吧。。
代碼：
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