hdu 1160 || zoj 1108 FatMouse's Speed

本文主要是介绍hdu 1160 || zoj 1108 FatMouse's Speed，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

水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;
}

这篇关于hdu 1160 || zoj 1108 FatMouse's Speed的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---