越大越聪明吗？
这是一道动态规划题目，这里只提供个人代码：
 #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!=-1) return;
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;
}
|