Sephiroth's boring days!!!

Love just for you.

聚会的快乐

题目见ural1039

  1: #include <stdio.h>
  2: #include <stdlib.h>
  3: #include <iostream>
  4: #define maxn 6010
  5: using namespace std;
  6: 
  7: struct ss
  8: {
  9:     int ro,nu;
 10: } a[maxn];
 11: int w[maxn];
 12: int f[maxn][2];
 13: int n;
 14: int x,y;
 15: int t[maxn];
 16: 
 17: int cmp(const void*a,const void*b)
 18: {
 19:     ss c=*(ss*)a,d=*(ss*)b;
 20:     if (c.ro<d.ro) return -1;
 21:     if (c.ro>d.ro) return 1;
 22:     return 0;
 23: }
 24: 
 25: void dp(int x)
 26: {
 27:     if (f[x][1]) return;
 28:     for (int i=t[x];i<t[x+1];++i)
 29:     {
 30:         int k=a[i].nu;
 31:         dp(k);
 32:         f[x][1]+=f[k][0];
 33:         f[x][0]+=max(f[k][0],f[k][1]);
 34:     }
 35:     f[x][1]+=w[x];
 36: }
 37: 
 38: int main()
 39: {
 40:     freopen("party.in","r",stdin);
 41:     freopen("party.out","w",stdout);
 42:     
 43:     scanf("%d",&n);
 44:     for (int i=1;i<=n;++i) scanf("%d",&w[i]);
 45:     scanf("%d%d",&x,&y);
 46:     while (!((!x)&&(!y)))
 47:     {
 48:         a[x].nu=x;
 49:         a[x].ro=y;
 50:         scanf("%d%d",&x,&y);
 51:     }
 52:     for (int i=1;i<=n;++i)
 53:         if (!a[i].ro)
 54:             a[i].nu=i;
 55:     a[0].ro=-1;
 56:     qsort(a,n+1,sizeof(ss),cmp);
 57:     for (int i=1;i<=n;++i)
 58:         if (!t[a[i].ro])
 59:             t[a[i].ro]=i;
 60:     t[n+1]=n+1;
 61:     for (int i=n;i>0;--i)
 62:         if (!t[i])
 63:             t[i]=t[i+1];
 64:     dp(0);
 65:     printf("%d\n",max(f[0][1],f[0][0]));
 66:     return 0;
 67: }
 68: 

posted on 2010-09-02 19:15 Sephiroth Lee 阅读(157) 评论(0)  编辑 收藏 引用 所属分类: 信息奥赛


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


free counters