水dp
检查了几天 cmp函数写错了 给跪了
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <map> #define inf 0x3f3f3f3f using namespace std; struct node { int w,v,id; }m[1010]; int cmp(node a,node b) { if(a.w<b.w) return 1; if(a.w==b.w&&a.v>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<i;j++) { if(dp[j]+1>dp[i] && m[j].w<m[i].w && m[j].v>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; }