ACMboy

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  4 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks

常用链接

留言簿

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

                                                               越大越聪明吗?
                 这是一道动态规划题目,这里只提供个人代码:

#include <iostream>
struct elephone
{
    
int weight,iq,num;
}
;
int k,s[1001],max=0,vis[1001],S[1001],dp[1001][1001];
elephone a[
1000];

void dpf(int i,int j)
{
    
int &ans=dp[i][j];
    
if(ans!=-1return;
    ans
=1;
    s[j]
=a[i].num+1;
    
if(j>max) {for(int q=1;q<=j;q++) S[q]=s[q];max=j;}
    
for(int p=0;p<k;p++)
    
{
        
if(!vis[p]&&a[p].weight>a[i].weight&&a[p].iq<a[i].iq)
        
{
            vis[p]
=1;
            dpf(p,j
+1);
            vis[p]
=0;
        }

    }

}

int main()
{
    
int i=0;
    memset(dp,
-1,sizeof(dp));
    memset(vis,
0,sizeof(vis));
    
while(scanf("%d%d",&a[i].weight,&a[i].iq)==2)
    
{
        a[i].num
=i;
        
++i;
    }

    k
=i;
    
for(int q=0;q<k;q++)
    
{
    vis[q]
=1;
    dpf(q,
1);
    vis[q]
=0;
    }

    printf(
"%d\n",max);
    
for(int r=1;r<=max;r++)
        printf(
"%d\n",S[r]);
    
return 0;
}





         
posted on 2010-04-09 13:58 EG-HUA 阅读(192) 评论(0)  编辑 收藏 引用

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