dp打开思路2：POJ2533 HDU1114 HDU1260 HDU1160（水题不水）

悠悠 2022-05-17 00:49 181阅读 0赞

题目：[https://vjudge.net/contest/68966\#overview][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];
    	}
    }

[https_vjudge.net_contest_68966_overview]: https://vjudge.net/contest/68966#overview