HDU 1160FatMouse's Speed代码错哪了
HDU 1160FatMouse's Speed代码哪里错了?
//这道题提交了n次,还是wa。无语了。请教各位一下下面的代码到底哪里错了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define MAX 1001
using namespace std;
typedef struct Mice{
int weight,speed,ID;
}Mouse;
//data
Mouse mouse[MAX+1];
int path[MAX+1];
int tmp[MAX+1];
int dp[MAX+1];
//function declaration
bool cmp(const Mouse&,const Mouse&);
int main(){
int i=0,j,k,n,max_len,max;
while((scanf("%d%d",&(mouse[i].weight),&mouse[i].speed))!=EOF ){
mouse[i].ID=i+1;
++i;
}
n=i;
//sort the struct Mouse by weight
sort(mouse,mouse+n,cmp);
dp[0]=1;
path[0]=-1;
for(i=1,k=0;i<n;++i){
max_len=0;
path[i]=-1;
for(j=i-1;j>=0;--j){
if(mouse[i].weight>mouse[j].weight &&
mouse[i].speed<mouse[j].speed && max_len<dp[j]){
max_len=dp[j];
path[i]=j;
k=i;
}
}
dp[i]=max_len+1;
}
printf("%d\n",dp[n-1]);
i=0;
while(k!=-1){
tmp[i]=k;
k=path[k];
++i;
}
for(j=i-1;j>=0;--j)
printf("%d\n",mouse[tmp[j]].ID);
return 0;
}
bool cmp(const Mouse &a,const Mouse &b){
if(a.weight==b.weight)
return a.speed>b.speed;
return a.weight<b.weight;
}
------解决方案--------------------
1 5
2 4
3 3
4 6
------解决方案--------------------
>printf("%d\n",dp[n-1]);
问题在这句
//这道题提交了n次,还是wa。无语了。请教各位一下下面的代码到底哪里错了。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define MAX 1001
using namespace std;
typedef struct Mice{
int weight,speed,ID;
}Mouse;
//data
Mouse mouse[MAX+1];
int path[MAX+1];
int tmp[MAX+1];
int dp[MAX+1];
//function declaration
bool cmp(const Mouse&,const Mouse&);
int main(){
int i=0,j,k,n,max_len,max;
while((scanf("%d%d",&(mouse[i].weight),&mouse[i].speed))!=EOF ){
mouse[i].ID=i+1;
++i;
}
n=i;
//sort the struct Mouse by weight
sort(mouse,mouse+n,cmp);
dp[0]=1;
path[0]=-1;
for(i=1,k=0;i<n;++i){
max_len=0;
path[i]=-1;
for(j=i-1;j>=0;--j){
if(mouse[i].weight>mouse[j].weight &&
mouse[i].speed<mouse[j].speed && max_len<dp[j]){
max_len=dp[j];
path[i]=j;
k=i;
}
}
dp[i]=max_len+1;
}
printf("%d\n",dp[n-1]);
i=0;
while(k!=-1){
tmp[i]=k;
k=path[k];
++i;
}
for(j=i-1;j>=0;--j)
printf("%d\n",mouse[tmp[j]].ID);
return 0;
}
bool cmp(const Mouse &a,const Mouse &b){
if(a.weight==b.weight)
return a.speed>b.speed;
return a.weight<b.weight;
}
------解决方案--------------------
1 5
2 4
3 3
4 6
------解决方案--------------------
>printf("%d\n",dp[n-1]);
问题在这句