题目：https://vjudge.net/contest/68966#overview

POJ2533

最长上升子序列，很平常的题，但是维持单调队列+二分还是值得一贴的，O(nlogn)

关键思想：出现在单调队列里的数都在当前接收的数之前，所以找到最小的比他大的数替换即可，而替换的位置其实就相当于它的DP[i]，只是已经没有记录的必要了。如果是当前最大就放到最后，cnt++。

最后单调数组长度就是所求，并且数组内的数组成的就是最长上升序列。

 （对萌新通俗点说，一个数比你先出现，还比你大，dp值还一样，那他肯定已经没用了）

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int maxn = 1005;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int Binary_Search(int *a,int left,int right,int element)//二分标准写法，用熟
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int l = left;
     
    
   

    

     

    
    

     
	int r = right;
     
    
   

    

     

    
    

     
	int mid;
     
    
   

    

     

    
    

     
	while(l < r)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		mid = (l + r) / 2;
     
    
   

    

     

    
    

     
		if(a[mid] <= element) l = mid + 1;
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      			r = mid;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return l;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int m;
     
    
   

    

     

    
    

     
	int i;
     
    
   

    

     

    
    

     
	while(cin>>m)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		int t;
     
    
   

    

     

    
    

     
		int cnt;
     
    
   

    

     

    
    

     
		int a[maxn];
     
    
   

    

     

    
    

     

      		cnt = 0;
     
    
   

    

     

    
    

     
		scanf("%d",&a[0]);
     
    
   

    

     

    
    

     

      		cnt++; //一个元素插入队列 
     
    
   

    

     

    
    

     
		//cout<<cnt<<endl;
     
    
   

    

     

    
    

     
		for(i=1;i<m;i++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			scanf("%d",&t);
     
    
   

    

     

    
    

     
			if(t > a[cnt-1])
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       a[cnt++] = t;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     
			else
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     

       a[Binary_Search(a,0,cnt,t)] = t;
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		printf("%d",cnt);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;	
     
    
   

    

     

    
    

     

      } 
     
    
  
 

HDU1114

背包题：经典背包求最大利益，这是求最小可能利益

所以，状态转移方程是这样：dp[j] = min(dp[j],dp[j-wei[i]]+val[i]);没必要贴代码

HDU1260

递推，姑且叫一维dp吧，不难，对当前人就两种选择，自己买，或者和上一个人一起买

所以dp[i][1]=dp[i-1][0]+y[i]-x[i-1];

dp[i][0]=min(dp[i-1][0],dp[i-1][1])+x[i];

dp[i][0]表示第i个人单独买票，dp[i][1]表示第i个人和前面的人一起买票。和以前一道题类似。也没必要贴代码

HDU1160

也是简单变形，先按照重量排序，然后找出LIS最长上升子序列就可以了。

排序，记录，回溯，操作略麻烦，而且是挺好的题，代码就贴出来。

  

   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<string.h> 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      struct Mice{
     
    
   

    

     

    
    

     
	int w,v,id;
     
    
   

    

     

    
    

     

      }mice[1010];
     
    
   

    

     

    
    

     

      int dp[1010];
     
    
   

    

     

    
    

     

      int pre[1010];
     
    
   

    

     

    
    

     

      bool cmp(Mice a,Mice b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	return a.w>b.w;
     
    
   

    

     

    
    

     

      } 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int s=0;
     
    
   

    

     

    
    

     
	while(scanf("%d%d",&mice[s].w,&mice[s].v)!=EOF)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		mice[s].id=s+1;
     
    
   

    

     

    
    

     

      		s++;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	sort(mice,mice+s,cmp);
     
    
   

    

     

    
    

     
	memset(pre,-1,sizeof(pre));
     
    
   

    

     

    
    

     
	for(int i=0;i<s;i++)
     
    
   

    

     

    
    

     

      		dp[i]=1;
     
    
   

    

     

    
    

     
	for(int i=0;i<s;i++)
     
    
   

    

     

    
    

     
		for(int j=0;j<i;j++)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			if(mice[j].w>mice[i].w&&mice[j].v<mice[i].v)
     
    
   

    

     

    
    

     

      			{
     
    
   

    

     

    
    

     
 if(dp[i]<dp[j]+1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       dp[i]=dp[j]+1;
     
    
   

    

     

    
    

     

       pre[i]=j;//注意记录
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
	int ans=0;
     
    
   

    

     

    
    

     
	int p;
     
    
   

    

     

    
    

     
	for(int i=0;i<s;i++)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if(dp[i]>ans)
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     

      			ans=dp[i];
     
    
   

    

     

    
    

     

      			p=i;
     
    
   

    

     

    
    

     

      		}		
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	printf("%d\n",dp[p]);
     
    
   

    

     

    
    

     
	while(p!=-1)//回溯
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("%d\n",mice[p].id);
     
    
   

    

     

    
    

     

      		p=pre[p];
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/81393716