Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 1949 Chores---DP

Posted on 2009-08-25 22:21 Uriel 阅读(351) 评论(0)  编辑 收藏 引用 所属分类: POJDP
注意,所有Chores是拓扑排序过的,就不算难了。。
不过自己很菜啊。。还是搞了好一会儿
/*Problem: 1949  User: Uriel 
   Memory: 4268K  Time: 375MS 
   Language: C++  Result: Accepted
*/
 

#include
<stdio.h>
#include
<stdlib.h>
#include
<string.h>

int n,i,j,x[10001],dp[10001],p[10001][101],t[10001],ans,MIN[10001];

int max(int a,int b)
{
    
return a>b?a:b;
}


int main()
{
    scanf(
"%d",&n);
    
for(i=1;i<=n;i++)
    
{
        scanf(
"%d %d",&t[i],&x[i]);
        
for(j=0;j<x[i];j++)
        
{
            scanf(
"%d",&p[i][j]);
        }

    }

    
for(i=0;i<=n;i++)dp[i]=0;
    
for(i=1;i<=n;i++)
    
{
        
if(x[i]==0)dp[i]+=t[i];
        
else
        
{
            
for(j=0;j<x[i];j++)
            
{
                dp[i]
=max(dp[i],dp[p[i][j]]+t[i]);
            }

        }

    }

    ans
=0;
    
for(i=1;i<=n;i++)
    
{
        ans
=max(ans,dp[i]);
    }

    printf(
"%d\n",ans);
    system(
"PAUSE");
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理