python 如何做网站/百度搜图入口

最简单的DP。。。并且在被提示了考虑dp[i]为i结尾的子序列的最长子序列，各种姿势还是没做出来。。

把体重降序排列，就变成了求速度的最长上升子序列，输出正是按次要求，也不用再倒序；

n<1000

n^2复杂度足以；但是LIS有nlogn的算法：点击打开链接

/* ***********************************************
Author        :angon
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
#define REPP(i,k,n) for(int i=k;i<=n;i++)
#define scan(d) scanf("%d",&d)
#define scann(n,m) scanf("%d%d",&n,&m)
#define LL long long
#define maxn 1005
#define mod 100000007int dp[maxn],pre[maxn];
struct node
{int w,s;int id;
}t[maxn];bool cmp(node n1,node n2)
{return n1.w>n2.w || (n1.w==n2.w && n1.s<n2.s);
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n=1,edx;while(~scanf("%d%d",&t[n].w,&t[n].s)){t[n].id=n;pre[n]=0;dp[n]=1;n++;// if(n==10) break;}sort(t+1,t+n,cmp);//对体重降序排列，求速度的最长上升子序列int maxlen=-1;REP(i,1,n){REP(j,1,i){if(t[i].w < t[j].w && t[i].s > t[j].s && dp[i]<dp[j]+1) //如果dp[i]>dp[j]就没必要再管{dp[i]=dp[j]+1;pre[i]=j;if(dp[i]>maxlen){maxlen=dp[i];edx=i;}}}}printf("%d\n",maxlen);REP(i,0,maxlen){printf("%d\n",t[edx].id);edx=pre[edx];}return 0;
}

nlogn模版

#include <iostream>  
using namespace std;  
int find(int *a,int len,int n)//修改后的二分查找，若返回值为x，则a[x]>=n  
{  int left=0,right=len,mid=(left+right)/2;  while(left<=right)  {  if(n>a[mid]) left=mid+1;  else if(n<a[mid]) right=mid-1;  else return mid;  mid=(left+right)/2;  }  return left;  
}  int main(void)  
{  int n,a[100],c[100],i,j,len;//新开一变量len,用来储存每次循环结束后c中已经求出值的元素的最大下标  while(cin>>n)  {  for(i=0;i<n;i++)  cin>>a[i];  b[0]=1;  c[0]=-1;  c[1]=a[0];  len=1;//此时只有c[1]求出来，最长递增子序列的长度为1.  for(i=1;i<n;i++)  {  j=find(c,len,a[i]);  c[j]=a[i];  if(j>len)//要更新len,另外补充一点：由二分查找可知j只可能比len大1  len=j;//更新len  }  cout<<len<<endl;  }  return 0;  
}