水dp
检查了几天 cmp函数写错了 给跪了
#include #include #include #include #include #include #include #include #include #define inf 0x3f3f3f3f using namespace std; struct node { int w,v,id; }m[1010]; int cmp(node a,node b) { if(a.w b.v) return 1; return 0; } int n,dp[1010],last[1010],ans,cnt,aaa[1010],tmp; int main() { int i,j; n=1; while(~scanf("%d%d",&m[n].w,&m[n].v)){ m[n].id=n; dp[n]=1; n++; } n--; sort(m+1,m+n+1,cmp); memset(last,0,sizeof last); ans=cnt=0; for(i=2;i<=n;i++) { for(j=1;j dp[i] && m[j].w m[i].v) { dp[i]=dp[j]+1; last[i]=j; if(dp[i]>ans) { ans=dp[i]; cnt=i; } } } } printf("%d\n",ans); tmp=cnt;i=0; while(tmp!=0) { aaa[i++]=tmp; tmp=last[tmp]; } while(i--) printf("%d\n",m[aaa[i]].id); return 0; }