hdu 1160 FatMouse's Speed帮忙看看哪错了,为啥WA 5
#include<iostream>#include<algorithm>#include<cstring>usingnamespacestd;constintmm=10...
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int mm=1010;
class node
{
public:
int weight,speed,id;
}f[mm];
int dp[mm],path[mm];
int pos;
bool cmp(node a,node b)
{
if(a.weight!=b.weight)return a.weight<b.weight;
else return a.speed>b.speed;
}
int main()
{ pos=0;
while(cin>>f[pos].weight>>f[pos].speed)f[pos].id=++pos;
sort(f,f+pos,cmp);
for(int i=0;i<pos;i++)
dp[i]=1,path[i]=-1;
for(int i=pos-2;i>=0;i--)
{
for(int j=i+1;j<pos;j++)
if(f[i].speed>f[j].speed&&f[i].weight<f[j].weight)
{
if(dp[i]<dp[j]+1)dp[i]=dp[j]+1,path[i]=j;
}
///else if(dp[i]<dp[j])dp[i]=dp[j],path
}
int z,_max=0;
for(int i=0;i<pos;i++)
if(dp[i]>_max)_max=dp[i],z=i;
cout<<_max<<"\n";
while(1)
{ if(z==-1)break;
cout<<f[z].id<<"\n";
z=path[z];
}
} 展开
#include<algorithm>
#include<cstring>
using namespace std;
const int mm=1010;
class node
{
public:
int weight,speed,id;
}f[mm];
int dp[mm],path[mm];
int pos;
bool cmp(node a,node b)
{
if(a.weight!=b.weight)return a.weight<b.weight;
else return a.speed>b.speed;
}
int main()
{ pos=0;
while(cin>>f[pos].weight>>f[pos].speed)f[pos].id=++pos;
sort(f,f+pos,cmp);
for(int i=0;i<pos;i++)
dp[i]=1,path[i]=-1;
for(int i=pos-2;i>=0;i--)
{
for(int j=i+1;j<pos;j++)
if(f[i].speed>f[j].speed&&f[i].weight<f[j].weight)
{
if(dp[i]<dp[j]+1)dp[i]=dp[j]+1,path[i]=j;
}
///else if(dp[i]<dp[j])dp[i]=dp[j],path
}
int z,_max=0;
for(int i=0;i<pos;i++)
if(dp[i]>_max)_max=dp[i],z=i;
cout<<_max<<"\n";
while(1)
{ if(z==-1)break;
cout<<f[z].id<<"\n";
z=path[z];
}
} 展开
1个回答
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询